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

32·827 Posts
Default

Quote:
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