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 N1 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.
FrobeniusGrantham is indeed about 3x slower than MR.
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 32bit N anyway.

A further note: The N+1 and N1 factorizations just disguise what is going on.
What is really needed is to have enough KNOWN FACTORS of N1, 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 APRCL 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)