20030604, 19:03  #1 
May 2003
1100000_{2} Posts 
Factoring Fermat Numbers
Hello all,
just out of mathematical interest, I did some research on Factoring Fermat Numbers and some site said that you can numbers F(n) with n<24 using Prime95. I was just wondering how one would do that ? What's the worktodo.ini command for example ? Greetings, Axel Fox. 
20030604, 19:16  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}·5·7 Posts 
Fermat number factoring
Take a look at this thread under "Math":
http://www.mersenneforum.org/viewtopic.php?t=109 Up through F24, ECM is probably the most useful factoring method right now for Fermat numbers, although P1 factoring might be more effective on F25 and F26. The status page is at: http://www.mersenne.org/ecmf.htm The work listed there includes some effort by individuals using programs other than Prime95/mprime, notably Richard Crandall's C program. The last factor found by ECM was the 23digit factor of F18 found in April 1999 by McIntosh and Tardif using Crandall's program, and my opinion is that we are overdue for a new discovery! 
20030604, 19:31  #3 
May 2003
2^{5}×3 Posts 
Thank you very much for providing me this link.

20030604, 19:39  #4 
"Sander"
Oct 2002
52.345322,5.52471
4A5_{16} Posts 
What about running P1 on fermat numbers. Is it also more efficient to factor 2^(2N)1?

20030604, 19:50  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}·5·7 Posts 
You could experiment. On a Pentium4, it very well might be faster doing P1 on M67108864 than on P33554432 because the SSE2 optimizations are only implemented in the Mnumber code. I have discovered that running ECM on Pnumbers is more efficient on Pentium3 and AthlonXP chips than on Pentium4 machines, so my guess is that a fast Athlon might be the best machine for doing P1 on F25 and F26, and in fact a 2GHz Athlon would probably run faster on P33554432 than a 2GHz Pentium4 would on M67108864. Keep in mind that at these FFT sizes, memory availability is also an issue.

20030604, 20:43  #6 
May 2003
1100000_{2} Posts 
Another question. I'm experimenting a little bit with ECM on M8388608.
This enables me to find possible divisors for F22, F21, F20, ... Will the program tell me when I find a factor of one of these Fermat numbers or will is just say "M8388608 has a factor : XXXXXXXX" ? Axel Fox. 
20030604, 20:51  #7  
P90 years forever!
Aug 2002
Yeehaw, FL
1FDF_{16} Posts 
Quote:
Then the fun begins  finding which F number you've cracked! 

20030604, 21:08  #8 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
identifying factors
The program will just say something like:
ECM found a factor in curve #1, stage #2 Sigma=2049756470223819, B1=44000000, B2=4290000000. M32768 has a factor: 4659775785220018543264560743076778192897 (Actually, it will write this in the results.txt file, but also write something similar in the dialogue box.) Therefore, if you find a factor, you will have the problem of determining which Fermat number your factor actually belongs to. I can figure this out by starting with 2 and successively squaring modulo the factor: 2^2 mod (factor) = 4 4^2 mod (factor) = 16, etc. After 10 successive squarings, I get that 2^(2^10) mod 4659775785220018543264560743076778192897 = 4659775785220018543264560743076778192896, that is, this factor divides F10 = 2^(2^10) + 1. (This factor only turned up because I had deleted it from the lowm.txt file.) If I square the result one more time, I of course will find out that 2^(2^11) mod (factor) = 1. (Use your favorite large integer calculation package for this.) 
20030604, 22:32  #9 
May 2003
1100000_{2} Posts 
How do you mean, "This factor only turned up because I deleted it from the lowm.txt file." ? Do you have to put the lowm.txt file in the Prime95 directory ? And then it doesn't report factors already in there, or what ?

20030604, 22:40  #10 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
That is correct. If you have already started a curve, it is not too late. Download lowm.txt into the Prime95 directory, and perhaps you also need to stop and restart the program, I am not completely sure. Otherwise, the program will report a factor at the end of stage 1 which will be the product of several of the known factors.

20030604, 23:24  #11 
May 2003
96_{10} Posts 
Hmm, another question.
Since it seems to be possible that ECM gives you a composite factor, suppose I find a really large factor some day, how do I check wether the factor is a prime factor or a composite one ? PS : Sorry if my stupid questions are boring you. 
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 
Factoring Fermat numbers  siegert81  Factoring  12  20110203 13:55 
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 