## Re: sufficient test for primes with certificate

Expand Messages
• Dear David, thank you for your friendly help. ... 1. You are right with your counterexample that the certificate is not right. I hope you will enjoy this
Message 1 of 33 , Jul 16, 2012
Dear David,

thank you for your friendly help.

> Here is a counterexample with
> prime g, prime a, and composite p,
> for which every part of your 3-selfridge test
> is applied, including your recent desperate "wriggle".

1. You are right with your counterexample that
the certificate is not right.
I hope you will enjoy this statement.

2. You did not verify the point 4.
http://109.90.3.58/devalco/suf_helmes.htm#1
if i am right in understanding your program
[1+sqrt (2969)]^(p-1)=14278+18966*sqrt (2969)=/=1 mod 29539
which indicate that p is not a prime.

Last but not least, there remains a claim that
the test 1.-4. is a sufficient test for p=3 mod 4, slowly with in average 8 selfridges. This would be an improvement versus the AKS-test.

If you have fun and time, try to find one counterexample
which destroy the remaining test :-)

I think i have 40 years in the future in order to find some nice
algorithms and i hope that you will participate in some.

Greetings from the primes
Bernhard
>
> 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!"));}
>
> Counterexample!
>
> 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
--- 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.