mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2002-09-18, 22:50   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2002-09-19, 00:01   #2
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

23×32×113 Posts
Default

How much memory can this use? Will it use a pile if you let it?
Xyzzy is offline   Reply With Quote
Old 2002-09-22, 10:23   #3
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

1A916 Posts
Default 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
patrik is offline   Reply With Quote
Old 2002-09-22, 10:53   #4
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

52·17 Posts
Default

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

/Patrik
patrik is offline   Reply With Quote
Old 2002-09-22, 17:59   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2002-09-22, 23:57   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2002-09-23, 11:21   #7
Philippe
 

22×3×73 Posts
Default 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
  Reply With Quote
Old 2002-09-23, 16:16   #8
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7·1,069 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2002-09-24, 21:25   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2002-09-26, 10:22   #10
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

23×32×113 Posts
Default

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...
Xyzzy is offline   Reply With Quote
Old 2002-09-26, 14:55   #11
binarydigits
 
Aug 2002

22×13 Posts
Default

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.
binarydigits is offline   Reply With Quote
Reply

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

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.