## Re: sufficient test for primes with certificate

Expand Messages
• ... (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
"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
• ... 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:
:

> 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.