mersenneforum.org > Math Elliptic Curve Method factoring - Fermat numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2002-09-18, 22:50 #1 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3×373 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-19, 00:01 #2 Xyzzy     "Mike" Aug 2002 23×32×113 Posts How much memory can this use? Will it use a pile if you let it?
 2002-09-22, 10:23 #3 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 1A916 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, 10:53 #4 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 52·17 Posts This has in fact actually been done. I just discovered that the updated lowm.txt does inlcude these factors. /Patrik
 2002-09-22, 17:59 #5 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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. 3×373 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   22×3×73 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-23, 16:16 #8 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 7·1,069 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. 111910 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     "Mike" Aug 2002 23×32×113 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...
2002-09-26, 14:55   #11
binarydigits

Aug 2002

22×13 Posts

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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Other Mathematical Topics 52 2021-01-29 21:17 Dirac Factoring 11 2007-11-01 14:01 bongomongo Factoring 5 2006-12-21 18:19 Carlos Programming 0 2005-09-11 12:50 philmoore Math 2 2002-11-12 01:11

All times are UTC. The time now is 11:56.

Thu May 6 11:56:39 UTC 2021 up 28 days, 6:37, 0 users, load averages: 1.20, 1.51, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.