mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-12-25, 15:21   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

23×89 Posts
Default 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
MattcAnderson is offline   Reply With Quote
Old 2020-12-25, 16:04   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×3×523 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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
rogue is offline   Reply With Quote
Old 2021-01-05, 09:28   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

17×19×29 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2021-01-05, 14:34   #4
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

26 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Gary is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIMPS' second Fermat factor! rajula Factoring 103 2019-03-12 04:02
GIMPS' first Fermat factor! Prime95 Factoring 72 2014-06-07 09:41
New Fermat factor found! ET_ Factoring 5 2011-01-13 11:40
New Fermat factor! ET_ Factoring 21 2010-03-15 21:02
New Fermat factor! 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.