Thread: Fast isPrime() for n < 2^32 View Single Post 2011-04-20, 17:02   #15
R.D. Silverman

Nov 2003

32·827 Posts Quote:
 Originally Posted by R.D. Silverman You are correct. Poor choice of words on my part. One needs factored part up to N^1/6 for both (or N^1/3 for either N-1 or N+1). Of course, if you just factor up to N^1/6 and the cofactor is prp, one can do a descent to prove the latter prime. Frobenius-Grantham is indeed about 3x slower than M-R. What's fastest in practice? I don't know. I strongly suspect it would be platform and implementation dependent. I would ask: Does it really matter? Any reasonable technique will only take a few microseconds for 32-bit N anyway.
A further note: The N+1 and N-1 factorizations just disguise what is going on.

What is really needed is to have enough KNOWN FACTORS of N-1, N+1,
N^2 + 1, N^2 + N + 1, N^2 - N + 1, etc. (any other low degree
cyclotomic polynomial in N) so that the product of those factors
exceeds N^1/3.

The APR-CL algorithm is, in a sense, an extension of this. It uses
partial factorizations of many cyclotomic polynomials in N, to
complete the proof. 'Many' basically means all such polynomials up to degree
(log N)^(logloglog N)  