View Single Post
Old 2011-05-31, 08:16   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1130210 Posts
Default

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

Paul
xilman is offline   Reply With Quote