View Single Post
Old 2020-11-06, 05:32   #22
Gary's Avatar
Aug 2015

26 Posts

Originally Posted by bbb120 View Post
I do not want to find any factor of Fermat number ,because it is very difficult to find one ,I only want to know the algorithm behind it
The programs I am familiar with will test each Dk = k*2^n + 1 for a range of k to see if it divides any Fermat number. To do this, the program will first use a sieve to eliminate all Dk that are divisible by any of the first X primes. X may vary from a few thousand to a huge number, depending on the value of n. For each Dk that survives the sieve, the program may immediately test to see if 2^2^m + 1 mod Dk = 0 for each m <= n-2 by doing successive square / mod operations. Or the program may next do a probable prime test on Dk before testing for Fermat number divisibilities. The PRP test is more efficient if the program is testing Dk to see if it divides either a Fermat number or a Generalized Fermat Number: a^2^n + b^2^n.

Hope that helps a bit.
Gary is offline   Reply With Quote