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 27·5 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

2×3×1,031 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 34·113 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

22·3·5 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 03:01.

Sun Jan 24 03:01:37 UTC 2021 up 51 days, 23:12, 0 users, load averages: 1.69, 1.56, 1.60