20110110, 06:55  #1 
Dec 2010
2·37 Posts 
Factoring Fermat numbers
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! 
20110110, 07:17  #2  
"Tapio Rajala"
Feb 2010
Finland
3^{2}·5·7 Posts 
Quote:
Quote:
Quote:
Ask for more information if you wish. I am sure there are many here that are happy to help you. 

20110110, 18:50  #3 
Dec 2010
2·37 Posts 
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). 
20110110, 21:39  #4 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10267_{8} Posts 
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.

20110111, 04:12  #5  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Quote:
whether k*2^{n+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. 

20110203, 09:34  #6 
"Matthew Anderson"
Dec 2010
Oregon, USA
2^{3}·149 Posts 
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.

20110203, 11:10  #7 
"Robert Gerbicz"
Oct 2005
Hungary
11001001011_{2} Posts 

20110203, 12:24  #8 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11·389 Posts 

20110203, 13:00  #9 
"Robert Gerbicz"
Oct 2005
Hungary
3^{2}·179 Posts 
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(n1) or F(n2),...
Last fiddled with by R. Gerbicz on 20110203 at 13:00 
20110203, 13:05  #10 
"Tapio Rajala"
Feb 2010
Finland
3^{2}×5×7 Posts 
One way to test all the possible Fermat numbers is to calculate (mod k*2^{n+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])^{2}. It seems that testing all the Fermat numbers is essentially as fast as testing only one.

20110203, 13:08  #11 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Celebrate with one year since that factorization of number F14
What I meant was that For example, 485*2^{338297}+1 was proved to be prime by Souichi Murata in May 2007 but the fact that it divides with that Fermat number F_{338295} 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? Last fiddled with by Raman on 20110203 at 13:34 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?  Erasmus  Math  46  20140808 20:05 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
Factoring Smallest Fermat Numbers  Erasmus  Factoring  32  20040227 11:41 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 