View Single Post
Old 2011-05-31, 08:16   #3
xilman's Avatar
May 2003
Down not across

11,423 Posts

Originally Posted by R.D. Silverman View Post
It is trivially known that any divisor p of 2^(2^n) + 1 must equal 1 mod
(2^(n+2)). I have given proofs on previous occasions. The proof
might be given as a homework problem in a first year number theory class.

This property is useful for trial division. It is often used to find small
divisors for large n. It isn't useful for much of anything else.
It's also of historical interest because it was used to speed the factorization of F_7 by Pollard's rho algorithm.

Pollard's rho isn't really of much use these days now that ECM is available.

xilman is offline   Reply With Quote