mersenneforum.org Factoring Fermat numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2011-01-10, 06:55 #1 siegert81   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,00020,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,0008,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!
2011-01-10, 07:17   #2
rajula

"Tapio Rajala"
Feb 2010
Finland

32·5·7 Posts

Quote:
 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.

Quote:
 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.

Quote:
 I began looking for proth primes of the form k*2^n+1 where 500,00020,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,0008,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.

 2011-01-10, 18:50 #3 siegert81   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).
2011-01-10, 21:39   #4
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102678 Posts

Quote:
 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.

2011-01-11, 04:12   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 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*2n+2+1 is a factor of 22[sup]n[/sup]+1 ?
for any specific, given value of k, for some particular value of that variable n.

2011-02-03, 09:34   #6
MattcAnderson

"Matthew Anderson"
Dec 2010
Oregon, USA

23·149 Posts

Quote:
 Originally Posted by Raman What is the algorithm that is being actually used to test out whether k*2n+2+1 is a factor of 22[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.

2011-02-03, 11:10   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

110010010112 Posts

Quote:
 Originally Posted by MattcAnderson Or, I could be wrong.
Yes, totally wrong.

2011-02-03, 12:24   #8
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts

Quote:
 Originally Posted by R. Gerbicz Yes, totally wrong.
How does it work? Is it simply that Fn is calculated mod k*2n+2+1, or is there a more efficient algorithm? I can't find anything about it by googling.

2011-02-03, 13:00   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts

Quote:
 Originally Posted by Mini-Geek How does it work? Is it simply that Fn is calculated mod k*2n+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),...

Last fiddled with by R. Gerbicz on 2011-02-03 at 13:00

2011-02-03, 13:05   #10
rajula

"Tapio Rajala"
Feb 2010
Finland

32×5×7 Posts

Quote:
 Originally Posted by Mini-Geek How does it work? Is it simply that Fn is calculated mod k*2n+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*2n+2+1) first 22[SUP]0[/SUP]+1 and then continue to 22[SUP]1[/SUP]+1 and so on up to 22[SUP]n[/SUP]+1 by simply using the squaring 22[SUP]m+1[/SUP] = (22[SUP]m[/SUP])2. It seems that testing all the Fermat numbers is essentially as fast as testing only one.

 2011-02-03, 13:08 #11 Raman 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*2338297+1 was proved to be prime by Souichi Murata in May 2007 but the fact that it divides with that Fermat number F338295 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 2011-02-03 at 13:34

 Similar Threads Thread Thread Starter Forum Replies Last Post Erasmus Math 46 2014-08-08 20:05 philmoore Math 131 2006-12-18 06:27 T.Rex Math 4 2005-05-07 08:25 Erasmus Factoring 32 2004-02-27 11:41 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 07:52.

Thu Feb 2 07:52:58 UTC 2023 up 168 days, 5:21, 1 user, load averages: 0.92, 0.90, 0.85