View Single Post
Old 2020-11-06, 05:15   #20
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
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
Gary has already hinted at it: "Sieve+trial division".

Trial division is the process that actually determines the factor. It uses modular exponentiation to check if the Fermat number is 0 modulo the potential factor. The process is similar to that for Mersenne's, which is well described here: https://www.mersenne.org/various/mat...rial_factoring

The sieve portion is a preprocessing step that eliminates numbers that can't be factors, leaving fewer to check for divisibility.
bsquared is offline   Reply With Quote