mersenneforum.org (https://www.mersenneforum.org/index.php)
-   FermatSearch (https://www.mersenneforum.org/forumdisplay.php?f=133)
-   -   possible overlapping Fermat factor ranges (https://www.mersenneforum.org/showthread.php?t=26338)

 MattcAnderson 2020-12-25 15:21

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 [URL="fermatsearch.org"]fermatsearch.org[/URL].

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,
[URL="http://www.prothsearch.com/fermat.html"]http://www.prothsearch.com/fermat.html[/URL]
All the k values are odd.

Regards,
Matt

 rogue 2020-12-25 16:04

[QUOTE=MattcAnderson;567303]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 [URL="fermatsearch.org"]fermatsearch.org[/URL].

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,
[URL="http://www.prothsearch.com/fermat.html"]http://www.prothsearch.com/fermat.html[/URL]
All the k values are odd.

Regards,
Matt[/QUOTE]

AFAIK, they eliminate even k. I know that gfndsieve does so I assume the others do as well.

 LaurV 2021-01-05 09:28

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).

 Gary 2021-01-05 14:34

[QUOTE=LaurV;568454]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).[/QUOTE]

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.

 All times are UTC. The time now is 03:37.

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