Quote:
Originally Posted by bsquared
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.

Quote:
Originally Posted by bsquared
The sieve portion is a preprocessing step that eliminates numbers that can't be factors, leaving fewer to check for divisibility

How to sieve ? I only know p=k*2^(n+2)+1 must be a prime,
so we can use primality to sieve any potential p=k*2^(n+2)+1,
is there any more efficient method to sieve potential p=k*2^(n+2)+1?