## Re: sufficient test for primes with certificate

Expand Messages
• ... Here are some [g, a, p] certificates that falsely declare composite p to be prime, using your 1-selfridge test: [1018080, 30271, 1048351] [74061, 13880,
Message 1 of 33 , Jul 16, 2012
"bhelmes_1" <bhelmes@...> wrote:

> thanks a lot that you reveal a hole in the proof
> and in the algorithm.
>
> You will surely remark that both counterexample are
> of the form a=16 and a=121 and that they are squares.

Here are some [g, a, p] "certificates" that
falsely declare composite p to be prime,

[1018080, 30271, 1048351]
[74061, 13880, 1060459]
[218703, 77606, 1072567]
[1023125, 73658, 1096783]
[135574, 98605, 1052651]
[1009768, 51051, 1060819]
[160165, 1722, 1073071]
[844366, 240957, 1085323]
[1046524, 63303, 1109827]
[449585, 90843, 1113911]
[280945, 175930, 1093891]
[1015244, 58043, 1073287]
[903680, 182003, 1085683]
[823106, 274973, 1098079]
[1069351, 53520, 1122871]
[890564, 220127, 1110691]
[1030548, 105079, 1135627]
[175930, 31150, 1115111]
[993015, 130504, 1123519]
[336493, 1244, 1148743]
[14473, 34607, 1157551]
[1075413, 60934, 1136347]
[922341, 239518, 1161859]
[666074, 495929, 1162003]
[1064431, 123660, 1188091]

In each case:
p = 3 mod 4,
kronecker(a,p) = 1,
the "witness" a is /not/ a square in Z,
a^((p-1)/2) = 1 mod p
g^2*a = 1 mod p
and p is /not/ prime.

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

for(k=1,#v,u=v[k];f+=cert(u[1],u[2],u[3]));
print(f" counterexamples in "#v" attempts");

25 counterexamples in 25 attempts

Each of these 25 counterexamples destroys your
1-selfridge claim, even with your latest "wriggle"
that the "witness" a must not be a square in Z.

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.