 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 11111100002 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

5×1,307 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   "name field" Jun 2011 Thailand 2·3·5·7·47 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 Gostin"
Aug 2015
Texas, USA

67 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.  Thread Tools Show Printable Version Email this Page 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 20:17.

Mon Jan 24 20:17:47 UTC 2022 up 185 days, 14:46, 1 user, load averages: 1.71, 1.49, 1.45