Elliptic Curve Method factoring - Fermat numbers

philmoore · 2002-09-18, 22:50

Prime95 not only works efficiently at trial factoring and P-1 factoring, it also has an excellent Elliptic Curve Method (ECM) routine that works on numbers of the form 2^m-1 and 2^m+1. I've been using it to search for factors of Fermat numbers, numbers of the form 2^(2^n)+1 which Pierre de Fermat mistakenly thought were all prime. So far, I have used it on all values of n from 12 to 25. (The composite Fermat numbers from n = 5 to 11 are already completely factored.) For the range n = 10 to 25, the last nine factors discovered have all been discovered by the Elliptic Curve Method, and my estimate is that there should be two or three more small enough that ECM has a good chance to find them. The program runs random curves on a given exponent, choosing a new curve each time it finishes a run without success. Curves in the current search ranges take anywhere from a few hours to a few days to run. So far I have found 23 factors of Mersenne numbers by this method, but since the Fermat numbers have already been extensively searched, I'm not too surprised by my lack of success on them so far.

If this sounds interesting to you, I have three suggestions:

1) Read the help (readme) file for details and how to turn on the advanced menu on Prime95.

2) Download the files lowm.txt and/or lowp.txt into your Prime95 folder. If you want to search individual Fermat numbers one at a time, you only need lowp.txt, but actually searching is more efficient if you search on M-numbers. This is especially true for Pentium IV computers because of the SSE2 instructions, but I've found that even on Athlon computers or Pentium III or II computers, that searching on M-numbers is 3% to 15% more efficient.

3) Choose an exponent. For example, P131072 = 2^(2^17)+1 is the 17th Fermat number, but you may also run, for example, on M262144, which is the product of the 0th through the 17th Fermat numbers, and has the advantage that you could theoretically discover a new factor of any of the Fermat numbers F12 through F17. If you choose a large exponent, you will need to increase the memory allocation for the program, so this may limit, in effect, the size of the largest number you may test. I have tested F25 (P33554432) successfully using 384M of memory and I use at least half of that for F24, half again for F23, etc. But even modest sized exponents sometimes show a 10%-15% increase in speed during phase 2 with extra memory allocation. Experiment!

For your reference, I am currently running the following B1 bounds on M-numbers: (B2 is set automatically.)

M32768 (F12 through F14): B1=44,000,000
M131072 (F12 through F16): B1=11,000,000
M524288 (through F18): B1=3,000,000
M2097152 (through F20): B1=1,000,000
M8388608 (through F22): B1=250,000

(A curve on the first number takes about 10 hours on a 1900 MHz Pentium IV and about 18 hours on a 1400 MHz Athlon. A curve on this last number takes about a week on a 1400 MHz Athlon with 128M allocated.)

If anyone is interested and has questions, please ask!

Phil Moore

Xyzzy · 2002-09-19, 00:01

How much memory can this use? Will it use a pile if you let it?

patrik · 2002-09-22, 10:23

What's the purpose of the files lowm.txt and lowp.txt? Does prime95 divide by all known factors before starting ECM on a number? And does that increase the chance of finding a remaining factor? Or are they just there for prime95 not to report any already known factor?

If they are important then perhaps one should enter e.g. F0-F4 and all known factors of F5-F13 into lowm.txt as known factors of M32768 before running it. Or is prime95 smart enough to look in lowp.txt if you are factoring M(2^n)?

Patrik Johansson

patrik · 2002-09-22, 10:53

This has in fact actually been done. I just discovered that the updated lowm.txt does inlcude these factors.

/Patrik

philmoore · 2002-09-22, 17:59

In response to the question of xyzzy on how much memory ECM will use: I believe that Prime95 is limited to the daytime and nighttime memory allocations which can be set via the Options/CPU dialog box. Default is 8M. This appears to be sufficient for small exponents, but I have found that even for exponents the size of P131072 (F17), that allocating more memory, say 16M or 24M, speeds up stage 2 processing by 10% to 30% or so. The reason is that the program precomputes a number of Fourier transforms that ideally should reside in RAM rather than on disk for best results. 8M may be enough for the basic program but not enough for the all the FFT precomputation results. George Woltman says in the readme file that ECM requires a minimum of 192 times the FFT size. I do not know, however, if the FFT size for various size exponents is readily available anywhere. He says that P-numbers can take a larger FFT size than M-numbers, so for the 25th Fermat number, P33554432, I took as a guide on the benchmarks page the information that FFT size for M-numbers in this range is 1792 K-bytes. Round up to 2M per FFT and you get 384M needed, which seemed sufficient for the one curve I ran on this number. But I also have found that F20 (or P1048576) runs fine on 24M, a little faster on 40M. My guess is that the optimum memory follows a formula like (minimum memory for the code) + 192*(FFT size). I will ask George Woltman if he has any additional information on this.

As to the question of Patrik on factors in the lowm.txt or lowp.txt files, it appears that the program does a consistency check when it starts a curve to be sure that these are actually factors of the number it is attempting to factor. However, the curve is run by doing calculations modulo the full number 2^n+/-1 and my understanding is that it is only at the end of each stage that the program does a GCD (Greatest Common Divisor) calculation to determine whether it has turned up any factors not listed in the lowm.txt or lowp.txt file. Incidentally, while testing whether the program worked correctly on 2^(2^n)-1 numbers, one test was to remove known factors from the lowm.txt file to see if the program could "rediscover" these factors. It has been quite successful so far considering the number of curves run, but I am still looking for the 40 digit factor of F10, the 49 digit factor of F9, and the 33 digit factor of F15. More curves!

Thanks for your questions!

Phil Moore

philmoore · 2002-09-22, 23:57

George Woltman just sent me the following information which I am passing on. I believe that for the Pentium-4, the crossover points may be slightly more conservative, but this should be enough information to estimate memory needs for ECM:

Hi,

Here are the V21 non-P4 FFT crossovers. 2^N+1 crossovers are the same
except the FFT size must be a power of 2.

759 32
945 40
1121 48
1501 64
1861 80
2201 96
2951 128
3671 160
4371 192
5841 256
7221 320
8651 384
10100 448
11520 512
14250 640
17000 768
19900 896
22650 1024
28350 1280
33700 1536
39200 1792
45100 2048
55800 2560
66300 3072
77400 3584
88900 4096
110000 5120
131000 6144
153100 7168
175000 8192
217000 10240
258400 12288
302500 14336
345500 16384
429000 20480
511000 24576
597000 28672
682000 32768
846000 40960
1010000 49152
1180000 57344
1348000 65536
1672000 81920
1999000 98304
2335000 114688
2665000 131072
3300000 163840
3945000 196608
4598000 229376
5255000 262144
6520000 327680
7760000 393216
9040000 458752
10330000 524288
12830000 655360
15300000 786432
17850000 917504
20400000 1048576
25350000 1310720
30150000 1572864
35100000 1835008
40250000 2097152
50000000 2621440
59400000 3145728
69100000 3670016
79300000 4194304

2002-09-23, 11:21

Hello

last year, I spent months to compute many curves of fermat numbers with p95 v21 on a PC without access to internet. I just downloaded the program from another computer. That's why I didn't have access to the lowp.txt files. So, the curves rediscovered the known factors each time. And here, I noticed a strange fact : when you ran a row of, for example, 100 curves for F12, the first one ALWAYS find factors and then the next ones with a "normal" probability (for example 50 % to find a small f12 factor with b1=11000000). I did test it with large amount of curves, with small or large B1's. I send my complete results file to Mr WOLTMAN, asking him this question but he answered all was OK. I do believe him but (eeerh, in fact, I didn't completely believe him...;)):

has someone noticed this problem ? is it reproductible? (I had a celeron 400 )
couldn't we imagine a pseudo-random number generator problem? (how is the seed computed for the first curve? with the date as in gmp-ecm?)

As I couldn't find a solution to this problem, I joined another factoring project but it would interest me to have an answer.

Thanks.

Philippe

Prime95 · 2002-09-23, 16:16

If you run without a lowp.txt file the first curve reports all the factors it finds. The second curve reports any factors not found by the first curve, and so on until you exit prime95 and restart it.

philmoore · 2002-09-24, 21:25

Attached is an Excel spreadsheet and chart showing all known factors of Fermat numbers up to 2^(2^32)+1. Notice that 2^(2^n)+1 is prime for n=0,1,2,3,4 and that these numbers are completely factored for n=5 through 11. The complete set of data is available at http://www.prothsearch.net/fermat.html

Phil Moore

Xyzzy · 2002-09-26, 10:22

I found a factor tonight, and it ain't in lowm.txt! Is this a good one, or am I getting excited over nothing?

[code:1]Stage 1 complete. 1152466582 transforms, 1 modular inverses. Time: 2625.430 sec.
M4096 has a factor: 4533797969079998187896395234756340228327120018230672063369857139206452673745645938373167615[/code:1]
I think it is 91 digits long...

binarydigits · 2002-09-26, 14:55

Quote:

Originally Posted by Xyzzy

I found a factor tonight, and it ain't in lowm.txt! Is this a good one, or am I getting excited over nothing?

Sorry but that 91-digit number is composite; it is at least divisible by 5.

2002-09-18, 22:50	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19×59 Posts	Elliptic Curve Method factoring - Fermat numbers Prime95 not only works efficiently at trial factoring and P-1 factoring, it also has an excellent Elliptic Curve Method (ECM) routine that works on numbers of the form 2^m-1 and 2^m+1. I've been using it to search for factors of Fermat numbers, numbers of the form 2^(2^n)+1 which Pierre de Fermat mistakenly thought were all prime. So far, I have used it on all values of n from 12 to 25. (The composite Fermat numbers from n = 5 to 11 are already completely factored.) For the range n = 10 to 25, the last nine factors discovered have all been discovered by the Elliptic Curve Method, and my estimate is that there should be two or three more small enough that ECM has a good chance to find them. The program runs random curves on a given exponent, choosing a new curve each time it finishes a run without success. Curves in the current search ranges take anywhere from a few hours to a few days to run. So far I have found 23 factors of Mersenne numbers by this method, but since the Fermat numbers have already been extensively searched, I'm not too surprised by my lack of success on them so far. If this sounds interesting to you, I have three suggestions: 1) Read the help (readme) file for details and how to turn on the advanced menu on Prime95. 2) Download the files lowm.txt and/or lowp.txt into your Prime95 folder. If you want to search individual Fermat numbers one at a time, you only need lowp.txt, but actually searching is more efficient if you search on M-numbers. This is especially true for Pentium IV computers because of the SSE2 instructions, but I've found that even on Athlon computers or Pentium III or II computers, that searching on M-numbers is 3% to 15% more efficient. 3) Choose an exponent. For example, P131072 = 2^(2^17)+1 is the 17th Fermat number, but you may also run, for example, on M262144, which is the product of the 0th through the 17th Fermat numbers, and has the advantage that you could theoretically discover a new factor of any of the Fermat numbers F12 through F17. If you choose a large exponent, you will need to increase the memory allocation for the program, so this may limit, in effect, the size of the largest number you may test. I have tested F25 (P33554432) successfully using 384M of memory and I use at least half of that for F24, half again for F23, etc. But even modest sized exponents sometimes show a 10%-15% increase in speed during phase 2 with extra memory allocation. Experiment! For your reference, I am currently running the following B1 bounds on M-numbers: (B2 is set automatically.) M32768 (F12 through F14): B1=44,000,000 M131072 (F12 through F16): B1=11,000,000 M524288 (through F18): B1=3,000,000 M2097152 (through F20): B1=1,000,000 M8388608 (through F22): B1=250,000 (A curve on the first number takes about 10 hours on a 1900 MHz Pentium IV and about 18 hours on a 1400 MHz Athlon. A curve on this last number takes about a week on a 1400 MHz Athlon with 128M allocated.) If anyone is interested and has questions, please ask! Phil Moore

2002-09-22, 10:23	#3
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 651₈ Posts	lowm.txt and lowp.txt? What's the purpose of the files lowm.txt and lowp.txt? Does prime95 divide by all known factors before starting ECM on a number? And does that increase the chance of finding a remaining factor? Or are they just there for prime95 not to report any already known factor? If they are important then perhaps one should enter e.g. F0-F4 and all known factors of F5-F13 into lowm.txt as known factors of M32768 before running it. Or is prime95 smart enough to look in lowp.txt if you are factoring M(2^n)? Patrik Johansson

2002-09-22, 17:59	#5
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19×59 Posts	ECM memory usage In response to the question of xyzzy on how much memory ECM will use: I believe that Prime95 is limited to the daytime and nighttime memory allocations which can be set via the Options/CPU dialog box. Default is 8M. This appears to be sufficient for small exponents, but I have found that even for exponents the size of P131072 (F17), that allocating more memory, say 16M or 24M, speeds up stage 2 processing by 10% to 30% or so. The reason is that the program precomputes a number of Fourier transforms that ideally should reside in RAM rather than on disk for best results. 8M may be enough for the basic program but not enough for the all the FFT precomputation results. George Woltman says in the readme file that ECM requires a minimum of 192 times the FFT size. I do not know, however, if the FFT size for various size exponents is readily available anywhere. He says that P-numbers can take a larger FFT size than M-numbers, so for the 25th Fermat number, P33554432, I took as a guide on the benchmarks page the information that FFT size for M-numbers in this range is 1792 K-bytes. Round up to 2M per FFT and you get 384M needed, which seemed sufficient for the one curve I ran on this number. But I also have found that F20 (or P1048576) runs fine on 24M, a little faster on 40M. My guess is that the optimum memory follows a formula like (minimum memory for the code) + 192*(FFT size). I will ask George Woltman if he has any additional information on this. As to the question of Patrik on factors in the lowm.txt or lowp.txt files, it appears that the program does a consistency check when it starts a curve to be sure that these are actually factors of the number it is attempting to factor. However, the curve is run by doing calculations modulo the full number 2^n+/-1 and my understanding is that it is only at the end of each stage that the program does a GCD (Greatest Common Divisor) calculation to determine whether it has turned up any factors not listed in the lowm.txt or lowp.txt file. Incidentally, while testing whether the program worked correctly on 2^(2^n)-1 numbers, one test was to remove known factors from the lowm.txt file to see if the program could "rediscover" these factors. It has been quite successful so far considering the number of curves run, but I am still looking for the 40 digit factor of F10, the 49 digit factor of F9, and the 33 digit factor of F15. More curves! Thanks for your questions! Phil Moore

2002-09-22, 23:57	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19×59 Posts	FFT sizes George Woltman just sent me the following information which I am passing on. I believe that for the Pentium-4, the crossover points may be slightly more conservative, but this should be enough information to estimate memory needs for ECM: Hi, Here are the V21 non-P4 FFT crossovers. 2^N+1 crossovers are the same except the FFT size must be a power of 2. 759 32 945 40 1121 48 1501 64 1861 80 2201 96 2951 128 3671 160 4371 192 5841 256 7221 320 8651 384 10100 448 11520 512 14250 640 17000 768 19900 896 22650 1024 28350 1280 33700 1536 39200 1792 45100 2048 55800 2560 66300 3072 77400 3584 88900 4096 110000 5120 131000 6144 153100 7168 175000 8192 217000 10240 258400 12288 302500 14336 345500 16384 429000 20480 511000 24576 597000 28672 682000 32768 846000 40960 1010000 49152 1180000 57344 1348000 65536 1672000 81920 1999000 98304 2335000 114688 2665000 131072 3300000 163840 3945000 196608 4598000 229376 5255000 262144 6520000 327680 7760000 393216 9040000 458752 10330000 524288 12830000 655360 15300000 786432 17850000 917504 20400000 1048576 25350000 1310720 30150000 1572864 35100000 1835008 40250000 2097152 50000000 2621440 59400000 3145728 69100000 3670016 79300000 4194304

2002-09-23, 11:21	#7
Philippe 8716₁₀ Posts	maybe a problem with ECM Hello last year, I spent months to compute many curves of fermat numbers with p95 v21 on a PC without access to internet. I just downloaded the program from another computer. That's why I didn't have access to the lowp.txt files. So, the curves rediscovered the known factors each time. And here, I noticed a strange fact : when you ran a row of, for example, 100 curves for F12, the first one ALWAYS find factors and then the next ones with a "normal" probability (for example 50 % to find a small f12 factor with b1=11000000). I did test it with large amount of curves, with small or large B1's. I send my complete results file to Mr WOLTMAN, asking him this question but he answered all was OK. I do believe him but (eeerh, in fact, I didn't completely believe him...;)): has someone noticed this problem ? is it reproductible? (I had a celeron 400 ) couldn't we imagine a pseudo-random number generator problem? (how is the seed computed for the first curve? with the date as in gmp-ecm?) As I couldn't find a solution to this problem, I joined another factoring project but it would interest me to have an answer. Thanks. Philippe

2002-09-19, 00:01	#2
Xyzzy Aug 2002 8643₁₀ Posts	How much memory can this use? Will it use a pile if you let it?

2002-09-22, 10:53	#4
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 651₈ Posts	This has in fact actually been done. I just discovered that the updated lowm.txt does inlcude these factors. /Patrik

2002-09-23, 16:16	#8
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 8254₁₀ Posts	If you run without a lowp.txt file the first curve reports all the factors it finds. The second curve reports any factors not found by the first curve, and so on until you exit prime95 and restart it.

2002-09-24, 21:25	#9
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 1121₁₀ Posts	Fermat factors chart Attached is an Excel spreadsheet and chart showing all known factors of Fermat numbers up to 2^(2^32)+1. Notice that 2^(2^n)+1 is prime for n=0,1,2,3,4 and that these numbers are completely factored for n=5 through 11. The complete set of data is available at http://www.prothsearch.net/fermat.html Phil Moore

2002-09-26, 10:22	#10
Xyzzy Aug 2002 8643₁₀ Posts	I found a factor tonight, and it ain't in lowm.txt! Is this a good one, or am I getting excited over nothing? [code:1]Stage 1 complete. 1152466582 transforms, 1 modular inverses. Time: 2625.430 sec. M4096 has a factor: 4533797969079998187896395234756340228327120018230672063369857139206452673745645938373167615[/code:1] I think it is 91 digits long...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Help with series convergence in Fermat method of factoring	EdH	Other Mathematical Topics	52	2021-01-29 21:17
Elliptic curve method	Dirac	Factoring	11	2007-11-01 14:01
Elliptic factoring with points NOT on the curve	bongomongo	Factoring	5	2006-12-21 18:19
Fermat's factoring method with Gauss's inprovement	Carlos	Programming	0	2005-09-11 12:50
Elliptic Curve Method - the theory	philmoore	Math	2	2002-11-12 01:11