View Single Post
Old 2020-11-06, 05:24   #21
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 View Post
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?
bbb120 is offline   Reply With Quote