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

Re: sufficient test for primes with certificate

Expand Messages
  • djbroadhurst
    ... (where A^2 = a mod p) You make no reference to the Lucas test in your final certificate . So all that you seem to require for a final proof is that 1) p
    Message 1 of 33 , Jul 15, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

      > i make sure that a is a quadratic residuum by
      > calculating a^[(p-1)/2]=1 with p=3 mod 4

      Your web page makes the following claim:

      > you get a certificate (g, a, p)
      > In order to prove the certificate only one Selfridge
      > is needed because a^((p-1)/2) = 1 mod p has to verify
      > and (gA)^2=1 mod p has to verify.
      (where A^2 = a mod p)

      You make no reference to the Lucas test in your
      final "certificate". So all that you seem to
      require for a final "proof" is that

      1) p = 3 mod 4
      2) kronecker(a,p) = 1
      3) a^((p-1)/2) = 1 mod p
      4) g^2*a = 1 mod p

      or in Pari-GP the test

      {cert(g,a,p)=p%4==3&&kronecker(a,p)==1
      &&Mod(a,p)^((p-1)/2)==1&&Mod(g,p)^2*a==1;}

      \\ Example:

      g=3588;a=16;p=14351;
      if(cert(g,a,p)==1,print("Helmes says "p" is prime"));

      Helmes says 14351 is prime

      So you seem to have a problem, since 14351 is not prime.

      It is thus quite wrong to claim a 1-selfridge certificate.
      Rather I believe that you have a 3-selfridge PRP test
      that proves compositeness when it fails, yet does
      not prove primality when it succeeds.

      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.