Sorry, an error occurred while loading the content.

## Re: sufficient test for primes with certificate

Expand Messages
• ... Indeed there seems to be little obstacle to manufacturing Fermat plus Lucas pseudoprimes that are much larger, given Bernhard s unwise choice of a
Message 1 of 33 , Jul 19, 2012
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Counterexample with 25 digits!

Indeed there seems to be little obstacle to manufacturing
"Fermat plus Lucas" pseudoprimes that are much larger,
given Bernhard's unwise choice of a positive Kronecker symbol.
For example this 62-digit counterexample was found in 7 seconds,
which is less time than it takes to factor p by brute force:

{g=9982012609162784317210263215191345125837484159508891963337295;
a=4577317655410878067033652962262995530005977311539811603281218;
p=10549248000000000000000800652325984000000000015191702458402471;
if(p%4 == 3 && !issquare(p) && !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 with "#Str(p)" digits!"));}

Counterexample with 62 digits!

David (per proxy the pseudoprime gremlins)
• ... 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:
:
> 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.