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

 2003-06-04, 19:03 #1 Axel Fox     May 2003 11000002 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.
 2003-06-04, 19:16 #2 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 25·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 P-1 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 23-digit 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!
 2003-06-04, 19:31 #3 Axel Fox     May 2003 25×3 Posts Thank you very much for providing me this link.
 2003-06-04, 19:39 #4 smh     "Sander" Oct 2002 52.345322,5.52471 4A516 Posts What about running P-1 on fermat numbers. Is it also more efficient to factor 2^(2N)-1?
 2003-06-04, 19:50 #5 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 25·5·7 Posts You could experiment. On a Pentium-4, it very well might be faster doing P-1 on M67108864 than on P33554432 because the SSE2 optimizations are only implemented in the M-number code. I have discovered that running ECM on P-numbers is more efficient on Pentium-3 and Athlon-XP chips than on Pentium-4 machines, so my guess is that a fast Athlon might be the best machine for doing P-1 on F25 and F26, and in fact a 2GHz Athlon would probably run faster on P33554432 than a 2GHz Pentium-4 would on M67108864. Keep in mind that at these FFT sizes, memory availability is also an issue.
 2003-06-04, 20:43 #6 Axel Fox     May 2003 11000002 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.
2003-06-04, 20:51   #7
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

1FDF16 Posts

Quote:
 Originally Posted by Axel Fox 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" ?
It will just say M8388608 has a factor: xxxx

Then the fun begins - finding which F number you've cracked!

 2003-06-04, 21:08 #8 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 25×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.)
 2003-06-04, 22:32 #9 Axel Fox     May 2003 11000002 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 ?
 2003-06-04, 22:40 #10 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 25×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.
 2003-06-04, 23:24 #11 Axel Fox     May 2003 9610 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Erasmus Math 46 2014-08-08 20:05 siegert81 Factoring 12 2011-02-03 13:55 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

All times are UTC. The time now is 01:02.

Thu Feb 2 01:02:12 UTC 2023 up 167 days, 22:30, 1 user, load averages: 1.36, 1.13, 1.01