Re: sufficient test for primes with certificate
- Dear David,
> > with A quadratic residuumi changed the algorithm
> You cannot determine whether this is the case without
> factorizing the target. Your code seems to ask for a
> positive kronecker symbol (which you call "Jacobi").
> But that is not the same as what you assumed.
First of all i limit the search for p=3 mod 4
Instead of a strong probablistic test i make now
a probablistic test for A^[(p-1)/2]=1
As p=3 mod 4 (p-1)/2 is odd and therefore the pretest
makes sure that A is a quadratic residue.
The test is not very fast, because i need two pretest and two
test for the certificate in the average for proving primes,
that makes 8 Selfridges as i guess.
Nevertheless no factorisation of p-1 or p+1 is needed
The certificate could be verified very fast by two multiplication
and a modulo operation.
Perhaps there might be some improvement.
This test seems to be faster than the AKS-test which is an improvement.
Nice greetings from the primes
--- In email@example.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)