mersenneforum.org possible overlapping Fermat factor ranges
 Register FAQ Search Today's Posts Mark Forums Read

 2020-12-25, 15:21 #1 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 23×89 Posts possible overlapping Fermat factor ranges A Fermat number is F(m) = 2^(2^m) + 1. It has been shown that any factor of a Fermat number has the form k*2^n + 1. with n greater than or equal to m+2 This information is at fermatsearch.org. if k is not odd then we have an equivalent representation since 2*k*2^c + 1 = k*2^(c+1) + 1 I assume that mmff and other Fermat search programs only search for odd k because the even cases will be searched in increased exponent Also, in the log of known Fermat factors, http://www.prothsearch.com/fermat.html All the k values are odd. Regards, Matt
2020-12-25, 16:04   #2
rogue

"Mark"
Apr 2003
Between here and the

22×3×523 Posts

Quote:
 Originally Posted by MattcAnderson A Fermat number is F(m) = 2^(2^m) + 1. It has been shown that any factor of a Fermat number has the form k*2^n + 1. with n greater than or equal to m+2 This information is at fermatsearch.org. if k is not odd then we have an equivalent representation since 2*k*2^c + 1 = k*2^(c+1) + 1 I assume that mmff and other Fermat search programs only search for odd k because the even cases will be searched in increased exponent Also, in the log of known Fermat factors, http://www.prothsearch.com/fermat.html All the k values are odd. Regards, Matt
AFAIK, they eliminate even k. I know that gfndsieve does so I assume the others do as well.

Last fiddled with by rogue on 2020-12-25 at 16:04

 2021-01-05, 09:28 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 17×19×29 Posts If you think about how modular exponentiation works (square and shift), then you will see why even k's are not needed. To test if some q=k*2^n+1 divides some Fm, you start with 2, and square mod q. If you get -1, then q divides F1. If not, you square again, and if -1, then q divides F2. If not, you square again, and if -1, then q divides F3. If not, you square again, and if -1, then q divides F4. If not, you square again, and if -1, then q divides F5. Now you see why even k are not relevant? Say I want to see if q=296*2^13+1 divides F11 (n has to be at least m+2 from a well known theorem). Repeating the above square+mod nine times, you get that this q divides F9 and you stop. Because two Fermat numbers can't share a factor. Exactly the same result you will get if you try to test if q=37*2^16+1 divides F14 - you will run into "q divides F9" and stop after 9 steps (this is the same q). Last fiddled with by LaurV on 2021-01-05 at 09:30
2021-01-05, 14:34   #4
Gary

"Gary"
Aug 2015
Texas

26 Posts

Quote:
 Originally Posted by LaurV If you think about how modular exponentiation works (square and shift), then you will see why even k's are not needed. To test if some q=k*2^n+1 divides some Fm, you start with 2, and square mod q. If you get -1, then q divides F1. If not, you square again, and if -1, then q divides F2. If not, you square again, and if -1, then q divides F3. If not, you square again, and if -1, then q divides F4. If not, you square again, and if -1, then q divides F5. Now you see why even k are not relevant? Say I want to see if q=296*2^13+1 divides F11 (n has to be at least m+2 from a well known theorem). Repeating the above square+mod nine times, you get that this q divides F9 and you stop. Because two Fermat numbers can't share a factor. Exactly the same result you will get if you try to test if q=37*2^16+1 divides F14 - you will run into "q divides F9" and stop after 9 steps (this is the same q).
To elaborate a bit more, any k*2^n+1 with even k can always be represented as k'*2^n'+1 with k' odd and n' > n. For example, LaurV's 296*2^13+1 = 37*2^16+1. Most Fermat factor search programs will test a range of k for a particular value of n, then test the same range of k for n+1, etc. So testing even values of k for n is unnecessary because the corresponding k*2^n+1 will eventually be tested by you (or some other researcher) using an odd k with a larger n.

 Similar Threads Thread Thread Starter Forum Replies Last Post rajula Factoring 103 2019-03-12 04:02 Prime95 Factoring 72 2014-06-07 09:41 ET_ Factoring 5 2011-01-13 11:40 ET_ Factoring 21 2010-03-15 21:02 ET_ Factoring 42 2008-12-01 12:50

All times are UTC. The time now is 04:45.

Mon Apr 12 04:45:56 UTC 2021 up 3 days, 23:26, 1 user, load averages: 1.53, 1.72, 1.86