Loading ...
Sorry, an error occurred while loading the content.

Re: sufficient test for primes with certificate

Expand Messages
  • djbroadhurst
    ... I did verify that point and all your other points. See the test: g = 21283; a = 2969; p = 29539; {if(p%4 == 3 && !issquare(a) && kronecker(a,p) == 1 &&
    Message 1 of 33 , Jul 16 12:20 PM
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

      > You did not verify the point 4.

      I did verify that point and all your other points.

      See the test:

      g = 21283;
      a = 2969;
      p = 29539;

      {if(p%4 == 3 &&
      !issquare(a) &&
      kronecker(a,p) == 1 &&
      Mod(a,p)^((p-1)/2) == 1 &&
      Mod((1+x)*Mod(1,p),x^2-a)^((p-1)/2) == g*x &&
      Mod(g,p)^2*a == 1 &&
      !isprime(p), print(" Counterexample!"));}

      In the line

      > Mod((1+x)*Mod(1,p),x^2-a)^((p-1)/2) == g*x

      I work modulo p and modulo x^2-a.
      Here x is /any/ solution to x^2 = a mod p.
      (There are in fact, 4 such solutions
      since p is composite.)

      Now square that line and we get

      Mod((1+x)*Mod(1,p),x^2-a)^(p-1) == 1

      since (g*x)^2 = g^2*a mod p
      and the code tests that

      > Mod(g,p)^2*a == 1

      Hence this counterexample passes /every/
      test that you have imposed. You have
      no place left to hide your mistakes.

      Best wishes

      David
    • paulunderwooduk
      ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
      Message 33 of 33 , Sep 21, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        :
        > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/

        > I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
        > {
        > 0m32.374s pfgw64 (3-prp)
        > 1m9.876s pfgw64 -t
        > 1m53.535s pfgw64 -tp
        > 3m0.483s pfgw64 -tc
        > 5m12.972s pfgw64 scriptify
        > 4m4.811s gmp (-O3/no pgo)
        > 4m9.148 pari-gp
        > 1m15s theoretical Woltman implementation
        > }
        >

        I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
        {
        17.505s pfgw (3-prp)
        1m1.986s pfgw -tp
        1m13.789s gmp (-O3/no pgo)
        }

        Paul
      Your message has been successfully submitted and would be delivered to recipients shortly.