View Single Post
Old 2011-04-20, 17:02   #15
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

32·827 Posts

Originally Posted by R.D. Silverman View Post
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)
R.D. Silverman is offline   Reply With Quote