20020918, 22:50  #1 
"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 P1 factoring, it also has an excellent Elliptic Curve Method (ECM) routine that works on numbers of the form 2^m1 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 Mnumbers. 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 Mnumbers 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 Mnumbers: (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 
20020919, 00:01  #2 
Aug 2002
8643_{10} Posts 
How much memory can this use? Will it use a pile if you let it?

20020922, 10:23  #3 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
651_{8} 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. F0F4 and all known factors of F5F13 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 
20020922, 10:53  #4 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
651_{8} Posts 
This has in fact actually been done. I just discovered that the updated lowm.txt does inlcude these factors.
/Patrik 
20020922, 17:59  #5 
"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 Pnumbers can take a larger FFT size than Mnumbers, so for the 25th Fermat number, P33554432, I took as a guide on the benchmarks page the information that FFT size for Mnumbers in this range is 1792 Kbytes. 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 
20020922, 23:57  #6 
"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 Pentium4, 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 nonP4 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 
20020923, 11:21  #7 
8716_{10} 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 pseudorandom number generator problem? (how is the seed computed for the first curve? with the date as in gmpecm?) 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 
20020923, 16:16  #8 
P90 years forever!
Aug 2002
Yeehaw, FL
8254_{10} 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.

20020924, 21:25  #9 
"Phil"
Sep 2002
Tracktown, U.S.A.
1121_{10} 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 
20020926, 10:22  #10 
Aug 2002
8643_{10} 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... 
20020926, 14:55  #11  
Aug 2002
2^{2}·13 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with series convergence in Fermat method of factoring  EdH  Other Mathematical Topics  52  20210129 21:17 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Elliptic factoring with points *NOT* on the curve  bongomongo  Factoring  5  20061221 18:19 
Fermat's factoring method with Gauss's inprovement  Carlos  Programming  0  20050911 12:50 
Elliptic Curve Method  the theory  philmoore  Math  2  20021112 01:11 