Factoring Fermat numbers

[siegert81]

I just have some questions about what programs/approaches to take in order to find a new Fermat divisor.

If I wanted to find a factor of F20, what's the best program/approach? What if, instead, I wanted to find a factor of F200? F2000? F20000? F200000?

I began looking for proth primes of the form k*2^n+1 where 500,000<k<1,000,000 and n>20,000 (testing one n value at a time). So far, I've found dozens of primes, but none of them are Fermat factors.

I also began testing for 5,000,000<k<10,000,000 and n>8,000. I've found hundreds of primes at this level, but none of them are Fermat factors.

Do I need to just keep testing for much longer periods of time, or should I change my entire approach?

Thanks for any help!

[rajula]

Originally Posted by siegert81

If I wanted to find a factor of F20, what's the best program/approach?

The best approach is to use ECM. First look from http://mersenne.org/report_ECM/ where we are at with that and then start crunching away with GMP-ECM / Prime95.

What if, instead, I wanted to find a factor of F200? F2000? F20000? F200000?

For F200 and maybe F2000 I would use GMP-Fermat and for the larger ones I would sieve with the appropriate program and then use pfgw. Some information is at http://www.fermatsearch.org/download.html.

I began looking for proth primes of the form k*2^n+1 where 500,000<k<1,000,000 and n>20,000 (testing one n value at a time). So far, I've found dozens of primes, but none of them are Fermat factors.

I also began testing for 5,000,000<k<10,000,000 and n>8,000. I've found hundreds of primes at this level, but none of them are Fermat factors.

Do I need to just keep testing for much longer periods of time, or should I change my entire approach?

First of all, I recommend that you see from http://www.fermatsearch.org/stats/merge.php which ranges have been tested and which have been reserved for testing so that you are not redoing a range (if that is not your purpose). One possible way to join the search for the high n:s is to go to the PrimeGrip PRPNet Proth prime search -projects, see http://www.primegrid.com/forum_thread.php?id=3008.

Ask for more information if you wish. I am sure there are many here that are happy to help you.

[siegert81]

I have pfgw, but the help file is not orderly. Is there a help file or a website that explains how to use pfgw?

As for the ranges I'm testing, I did look to make sure I'm covering virgin territory. I checked the fermatsearch site, and I also verified that no Fermat factors have been found in these ranges (yet).

[TimSorbet]

Originally Posted by siegert81

I have pfgw, but the help file is not orderly. Is there a help file or a website that explains how to use pfgw?

There are quite a few help files, but the most important are pfgwdoc.txt, telling you what switches do what, and abcfileformats.txt, which provides details on the ABC file formats, which are commonly used to give to PFGW for it to test.

[Raman]

Originally Posted by rajula

For F200 and maybe F2000 I would use GMP-Fermat and for the larger ones I would sieve with the appropriate program and then use pfgw. Some information is at http://www.fermatsearch.org/download.html.

What is the algorithm that is being actually used to test out
whether k*2ⁿ⁺²+1 is a factor of 2^2[sup]n[/sup]+1 ?
for any specific, given value of k, for some particular value of that variable n.

[MattcAnderson]

Originally Posted by Raman

What is the algorithm that is being actually used to test out
whether k*2ⁿ⁺²+1 is a factor of 2^2[sup]n[/sup]+1 ?
for any specific, given value of k, for some particular value of that variable n.

As Far As I Know, first the k are seived to remove k candidates with 2^(n+2)+1 with small factors (maybee less than 30?). Then the remainder of 2^(2^n)+1 divided by k*2^(n+2)+1 is calculated. Since this number of digits in the Fermat number could be more than one billion and greater than available RAM, the number is loaded only a few bits at a time. In Binary, F(n) = 2^(2^n)+1 is a 1 followed by a long string of zeros and finally a one at the end. So, I imagine the computer performing long division like I learned in grade school and only remembering the temporary remainder. Every time, it checks if the remainder is one, or if it has gotten to the last digits of F(n). If k is not a factor, it chooses the next candidate for k, and does another long division. Or, I could be wrong.

[R. Gerbicz]

Originally Posted by MattcAnderson

Or, I could be wrong.

Yes, totally wrong.

[TimSorbet]

Originally Posted by R. Gerbicz

Yes, totally wrong.

How does it work? Is it simply that Fn is calculated mod k*2ⁿ⁺²+1, or is there a more efficient algorithm? I can't find anything about it by googling.

[R. Gerbicz]

Originally Posted by Mini-Geek

How does it work? Is it simply that Fn is calculated mod k*2ⁿ⁺²+1, or is there a more efficient algorithm? I can't find anything about it by googling.

Yes, and in this case the mod operation is easy, because k is *small*. And in fact the code checks the smaller Fermat numbers also, because it is possible that k*2^(n+2)+1 is a divisor of F(n-1) or F(n-2),...

[rajula]

Originally Posted by Mini-Geek

How does it work? Is it simply that Fn is calculated mod k*2ⁿ⁺²+1, or is there a more efficient algorithm? I can't find anything about it by googling.

One way to test all the possible Fermat numbers is to calculate (mod k*2ⁿ⁺²+1) first 2^2[SUP]0[/SUP]+1 and then continue to 2^2[SUP]1[/SUP]+1 and so on up to 2^2[SUP]n[/SUP]+1 by simply using the squaring 2^2[SUP]m+1[/SUP] = (2^2[SUP]m[/SUP])². It seems that testing all the Fermat numbers is essentially as fast as testing only one.

[Raman]

Celebrate with one year since that factorization of number F14

What I meant was that

For example, 485*2³³⁸²⁹⁷+1 was proved to be prime by Souichi Murata in May 2007
but the fact that it divides with that Fermat number F₃₃₈₂₉₅ was only being revealed upon August 21, 2007.
(that is exactly ten years before that USA total solar eclipse)
Why is this delay? What is actually the algorithm that is being used up
for this purpose of verifying divisibility of some Fermat number?

Is it brute force - just simply testing divisibility - that is in some way similar to one that is
being used by GIMPS for some trial factoring cases?