Factoring Fermat Numbers

Axel Fox · 2003-06-04, 19:03

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.

philmoore · 2003-06-04, 19:16

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!

Axel Fox · 2003-06-04, 19:31

Thank you very much for providing me this link.

smh · 2003-06-04, 19:39

What about running P-1 on fermat numbers. Is it also more efficient to factor 2^(2N)-1?

philmoore · 2003-06-04, 19:50

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.

Axel Fox · 2003-06-04, 20:43

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.

Prime95 · 2003-06-04, 20:51

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!

philmoore · 2003-06-04, 21:08

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.)

Axel Fox · 2003-06-04, 22:32

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 ?

philmoore · 2003-06-04, 22:40

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.

Axel Fox · 2003-06-04, 23:24

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.

2003-06-04, 21:08	#8
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵×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.)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
What are the Primality Tests ( not factoring! ) for Fermat Numbers?	Erasmus	Math	46	2014-08-08 20:05
Factoring Fermat numbers	siegert81	Factoring	12	2011-02-03 13:55
Elliptic Curve Method factoring - Fermat numbers	philmoore	Math	131	2006-12-18 06:27
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25
Factoring Smallest Fermat Numbers	Erasmus	Factoring	32	2004-02-27 11:41

2003-06-04, 19:03	#1
Axel Fox May 2003 1100000₂ 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. 2⁵·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 2⁵×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 4A5₁₆ 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. 2⁵·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 1100000₂ 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, 22:32	#9
Axel Fox May 2003 1100000₂ 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. 2⁵×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 96₁₀ 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.