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

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

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