Factoring highly composite Mersenne numbers

philmoore · 2003-08-20, 21:37

This thread is sort of a continuation to those started by wblipp on the factors of M5040. The numbers he has been working on have highly composite exponents, and I have been working on similarly composite exponents the past 5 weeks using a different method and Prime95, and wanted to share what I've found.

I've been interested in iterated Mersenne numbers M(M(n)) where M(n)=2^n-1 and n is not too large. Will Edgington has a web-page on these numbers for the case where M(n) is a Mersenne prime, but these are tough, and not too many factors are known. On the other hand, if n is composite, M(n) is even more so, and M(M(n)) (I'll just write MMn from now on) is highly composite. These numbers are roughly the size of the Fermat numbers, but in general, easier to factor because they have more factors. However, the method works on any M(n) for a composite n, so I'll describe it using M(30030) as an example. 30030=2*3*5*7*11*13, so for each proper factor m of 30030, M(m) is a factor of M(30030). Rather than work on just the primitive part of M(30030), which, if I understand correctly, is wblipp's method, I set up the lowm.txt file with all known factors of M(30030), including factors of M(15015), M(10010), M(6006), etc. (In practice, I only put in the factors up to 40 or 50 digits, as larger factors are unllikely to show up in ECM.) It takes quite a bit of work up front, but once done, I can run P-1 and ECM on M30030 and turn up factors of any smaller Mersenne subfactors as well. Since M(30030) has 2^6-1=63 distinct pieces, of which 10 are not yet completely factored, running a curve on M(30030) in effect attempts to find factors of 10 different Mersenne numbers simultaneously.

So, for example, I found the following factors running ECM and P-1 on M30030:

M3003: 148781787948190413131571457
M4290: 52441211236235251**
M5005: 118449316117077011675941481669521
M6006: 766701202212468052531
M10010: 20312320609781201
M10010: 140925959524554569735371
M15015: 1505297798475152441761
M15015: 11329238455344375886321
M30030: 6713804061670210489464481

The asterisks indicate that the primitive part of M4290 is now completely factored, as a 261-digit cofactor was also proven prime. (Unfortunately, M4290 is still not completely factored since M2145 is not, but P2145 is completely factored.)

A few points if you decide to do this.

1) You can use Will Edgington's files to find the factors for lowm.txt. Will normally does not list the largest factor of completely factored Mersennes to save space, so you may have to compute this, but if it is over 50 digits, you can probably safely skip it.

2) Will's files do not list repeated factors. For example, M21=7^2*127*337. One factor of 7 comes because M21 is divisible by M3=7, but the other comes since 21=3*7. He lists M21 as D (for done), but you have to recognize that there is another 7 to be taken out of the product M21/(M3*M7) before you get the final prime factor 337.

3) If you do this for an exponent divisible by 8, you will have to take into account Aurifeullian factorizations. I haven't had to do this, since all M(n) are odd, but you should be aware of this if you try it. Maybe wblipp can tell us how he handles this.

4) When you find a factor, you still do not know to what exponent it corresponds. I usually play around with MAPLE to figure this out, 2&^(30030/x)=1? for what values of x.

5) Occasionally, especially if you try P-1 factoring first, which I recommend especially on larger exponents, you may turn up several factors at once, which shows up as a large composite exponent. When this happens, I use Dario Alpern's java applet to quickly factor the composite into primes. (Thanks, Dario!)

Here are the factors I have found recently for iterated Mersenne numbers. In most cases, I ran P-1 and ECM on the full number, but for MM24, I ran a few curves on M69615, since 69615 is a factor of M24, and I can run more curves on M69615 than on MM24=M16777215. For n greater than 26, MMn is too large for Prime95 and I only ran on pieces.

factors found: (A couple of these may be already known, but most are new.)

MM15
M32767: 1068068525221937

MM16
M21845: 1211325473810854711
M65535: 11176078153580687409841
M65535: 1174653632931498493221732315481

MM18
M3591: 1423477480583686033801
M4161: 3672306633037027038343
M4161: 34415683896971856527721511
M4161: 50025948683707127142710139761032216969116361
M4599: 23762841504942692358991
M9709: 1352358807140765383
M9709: 2779222612409960558896559
M13797: 28696576370397202523719
M29127: 16267633913287
M29127: 5302845396960049
M29127: 1190654334109779234151
M37449: 34257210379744472627001409
M87381: 9772938708077706182408143
M262143: 137047273990488836451289

MM20
M6355: 32133782835946105615711
M13981: 711592027916639
M25575: 45769053349801
M33825: 1579241765314951
M69905: 50129015311
M69905: 49541108644483255361
M69905: 2495793068897706189481
M1048575: 33797174472601

MM21
M42799: 523337729993416956257

MM22
M15709: 1227801105600337
M47127: 75896431183
M47127: 1009531506607987236949561
M1398101: 44703303600503

MM24
M5355: 14454894086094092973322681
M10845: 1838659298945671
M13923: 2403085484872801
M15183: 49158399420079489
M21931: 75084924799115687
M25305: 797500182991
M28679: 37679387929
M28679: 175225535311
M28679: 22169463523201
M36873: 55478611690043041
M46995: 18678820681
M53261: 1381827990583
M61455: 841632124681
M69615: 22658482476631
M69615: 39859832812220636671
M75915: 122438536189831
M86037: 17159907577
M109655: 3171698838742791631
M159783: 1338562269409
M328965: 292120921
M328965: 335072816835121
M430185: 535177230470191
M798915: 4722853131361
M798915: 88547053762441
M798915: 11276411307405271
M1118481: 980956754885017
M1290555: 2119091311
M1864135: 44247108361
M2396745: 242301332521
M3355443: 185629817647

MM25
M1082401: 128667171673
M33554431: 13809930057809

MM26
M24573: 400436693401
M67108863: 54297512617849

MM27
M19173961: 114430199249

MM29
M486737: 52006801325877583

MM32
M196611: 64836016249
M327685: 7605486928751
M327685: 3626169746755001
M3342387: 73488882480103
M5570645: 22327145161
M16843009: 355286431847
M16711935: 645615472921

Any questions, I'll try to answer here in the forum. I think this is a viable way of attacking highly composite Mersenne exponents, and also rewarding in terms of the number of factors turned up.

Phil

alpertron · 2003-08-22, 12:17

I think that wblipp's approach is better.

Most of the time ECM code is doing modular multiplications. This means that the time needed to process a curve up to some bound is related to the square of the number of digits of the number to factor when you use Montgomery multiplications as in my applet or O(d^1.585) when you use Karatsuba multiplications for large numbers.

So if you know the factorization of a number in two or more composites, as in this case, it is faster to do ECM in the factors separately.

For example, it is twice as fast to perform ECM for the both numbers M(n) and M(n)+2 than for M(2n) if Montgomery multiplications are used and about 50% faster if Karatsuba multiplication is used.

philmoore · 2003-08-22, 22:52

I certainly agree with your heuristics, but you also must keep in mind that Prime95 uses DWT-based multiplication, which takes time on the order of O(n*ln n) where n is the number of digits in the number. So for large n, doubling the number of digits only slightly more than doubles the amount of time needed for a multiplication. However, since numbers have to be large in order for DWT to be advantageous, you can argue that the multiplication routines used in gmp-ecm might be better for numbers the size of those being factored by wblipp. Still, the Prime95 code is highly optimized and I'm not entirely convinced that its optimizations don't make this method competitive. Consider, in 5 weeks using just two 1600 MHz Pentium 4 computers, I have found 83 new factors, and 55 of these factors have been of Mersenne numbers with four or five digit exponents, i.e., comparable to the exponents being worked on by wblipp. Running 300 curves at B1=50,000 on M30030 took about 5 hours of P4 computer time on one of these computers, and running 700 curves at B1=250,000 took about 2.4 days. (B2=100*B1 is the default stage 2 bound.) It would be interesting to see a comparison to the time it would take a comparable machine running this number of curves on the 9 composites contained in M30030, which were originally a C145, C264, C278, C416, C428, C850, C868, C1724, and a C1735. (I am omitting the C177 from M1001 and the C212 from P1001 as these Cunningham numbers had already been searched to a fairly high limit and I did not expect to find any new factors.)

The other issue is set-up time, but as a certain amount of set-up can certainly be automated, perhaps it is currently more of an issue than it should be.

At any rate, so little work has been done on these Mersenne numbers with composite exponents, both of these methods certainly are proving fruitful.

Phil

smh · 2003-08-23, 07:58

A while ago i did some very limmited speed testing on Prime95 and GMP-ECM 5

On a P4, prime95 turned out to be about 4 times faster on mersenne numbers in stage 1 (Running 1M curves on M959 and M971).

Even taking of about 40 digits of known factors of M959 didn't make GMP-ECM faster, actually it was slower than factoring the full number. So you need a much smaller cofactor to make the use of GMP-ECM efficient.

On stage 2, prime95 is slightely faster (10%), but taking of that 40 digits of M959 makes that one about 10% faster.

I guess on a Athlon or P3 things will be different (maybe stage 2 og GMP-ECM much faster?)

wblipp · 2003-09-01, 19:15

Quote:

Originally Posted by philmoore

Any questions, I'll try to answer here in the forum. I think this is a viable way of attacking highly composite Mersenne exponents, and also rewarding in terms of the number of factors turned up.

1. What's the format for lown.txt? I'm guessing the lowm.txt file should follow the mersfmt format - each line is

M(<space>exponent<space>):C<space>factor

2. Where does lowm.txt go? I guessing in the prime95 directory.

3. Do you recommend using the advanced menu to trigger P-1 and ECM testing, or do you recommend editting the worktodo.ini file?

Xyzzy · 2003-09-01, 20:52

2 - Yes...

3 - I use the worktodo.ini file...

Quote:

The ECM choice lets you factor Mersenne numbers using the Elliptic Curve Method of factoring. Select a few exponents and bounds to factor from the http://www.mersenne.org/ecm.htm web pages. Note: You do not reserve exponents to work on, several people can do ECM factoring on the same exponent. The program uses a random number generator to select elliptic curves to test. You must email results to me at woltman@alum.mit.edu - primenet does not support ECM factoring. WARNING: ECM does not adhere to the memory limits specified in the Options / CPU dialog box. ECM requires a minimum of 192 times the FFT size. Thus, ECM factoring of F20 which uses a 64K FFT will use a minimum of 192 * 64K or 12MB of memory. You can also edit the worktodo.ini file directly. For example:

ECM=751,3000000,0,100,0,0,0,0

The first value is the exponent. The second value is bound #1. The third value is bound #2 - leave it as zero. The fourth value is the number of curves to test. The fifth value is no longer used. The sixth value is the specific curve to test - it is only used in debugging. The seventh value is 0 for 2^N-1 factoring, 1 for 2^N+1 factoring. The eighth value is no longer used.

wblipp · 2003-09-02, 23:22

Quote:

Originally Posted by philmoore

2) Will's files do not list repeated factors. For example, M21=7^2*127*337. One factor of 7 comes because M21 is divisible by M3=7, but the other comes since 21=3*7.

Is the rule for repeated factors:

If p is a primitive factor of M(n) then p is a repeated primitive factor of M(p*n).

(This assumes primitive factor means a factor of the the primitive polynomial - is that correct, or is there a different name for these repeated factors?)

wblipp · 2003-09-06, 04:09

Quote:

Originally Posted by philmoore

Any questions, I'll try to answer here in the forum.

I must be doing something wrong with the lowM.txt file. When I run Prime95 for the exponent 1575, it finds a large highly composite factor. The found factor includes, among other things, factors of M(315) that are listed in lowM.txt. The factor of M(315) is listed on a line that says

M( 315 )C: thefactor

The lowM.txt file is in the same directlory as Prime95.exe. I was running the ECM test from the GUI. What should I be doing differently?

patrik · 2003-09-06, 14:09

I think you have to enter the factors explicitly as factors of M1575. Make a new line
[code:1]M( 1575 )C: thefactor[/code:1]for each factor.

philmoore · 2003-09-23, 20:56

I just timed some curves running on a couple of Cunningham numbers on a 1900 MHz Pentium 4 and found something interesting. These curves were run to a stage 1 bound of 11,000,000 and the standard stage 2 bound of 100 times the stage 1 bound.

M1001:
stage 1, 208 seconds
stage 2, 115 seconds

P1001:
stage 1, 518 seconds
stage 2, 204 seconds

M2002:
stage 1, 310 seconds
stage 2, 147 seconds

The slowness on P1001 is easily understood to result from the fact that SSE2 instructions are not implemented in the multiplication code for P-numbers. However, the interesting thing is that the time to run a curve on M2002, which is equivalent to running a curve on M1001 and P1001 simultaneously, is only 37% more than the time to run on M1001 alone. I haven't checked, but I suspect that there is probably a similar gain on Athlon and Pentium 3 computers.

I should add that I needed to create entries for M2002 in the lowm.txt file in the Prime95 folder, but this was easily done by combining the existing factors for M1001 in lowm.txt and P1001 in lowp.txt.
(The files are available for download at http://www.mersenne.org/ecm.htm )
Note that the entries in lowm.txt must be ordered in increasing exponent size, so, for example, the entries for M2002 must come before the entries for M2003, but after entries for M1999, M2000, M2001, etc.

Less work has been done on the P-numbers in the Cunningham lists, but the following exponents are those for which both the P-number and the M-number are unfactored. I would suggest to those interested that running curves to stage 1 bounds of 11,000,000 and 44,000,000 on the double exponent number may be an efficient way to work on these unfactored Cunningham numbers. The complete list of exponents n for which Mn and Pn are both unfactored is:

761 787 791 799 805 811 823 827 853 859
863 877 887 893 905 913 923 933 947 949
961 991 1001 1009 1019 1021 1025 1027
1033 1037 1043 1051 1055 1067 1079 1087
1091 1105 1109 1115 1123 1127 1131 1133
1135 1137 1139 1147 1151 1153 1157 1159
1161 1163 1165 1167 1173 1175 1177 1179
1183 1187 1191 1193

wblipp · 2003-09-23, 23:31

It isn't clear which circumstances favor Prime95 over ECM. It's especially confusing for a project like ElevenSmooth that has already set up an ECM server and has some numbers tested to much higher levels than other numbers. Issues tilting toward Prime95 are P4 processors, many simultaneous factors, lightly factored numbers. and large numbers. I conducted some timing comparisons to help decide where Prime95 would best fit into the ElevenSmooth project. These comparisons were all made on a P2, so the Prime95 advantage on P4's isn't included in this.

The smallest composite in the ElevenSmooth project is the 149 digit factor from the 475 digit M(1575). As expected, ECM was faster for this - by a factor of 4. A fairer comparison would be a cluster of simultaneous numbers, but these are hard to find in the previously worked numbers because the combinable factors tend to be at different ECM levels. The best I could find was a cluster of three numbers in the low 300 digits that were close together. This clustering and lesser factoring helped Prime95, but ECM was still 2 time faster. A much larger cluster comes from the three largest composites from M(665280). These range from 10,000 to 40,000 digits. Prime95 was five times faster on these.

Clearly Prime95 is the better tool for working on the largest exponents. The ElevenSmooth project was at a transition point of having put all the factors of M(665280) into the ECM server, and ready to begin on the additional exponents of M(3326400) - those exponents that are multiples of 25.

Clearly the right way to start the multiples of 25 was to use Prime95. We've just finished the first stage at B1=2000, and we found 40 factors - see the other thread for details, but this compares to a total of 51 factors previously found for the M(665280) subset.

Longer term it probably makes sense to split some of the factors out into the ECM server, where they can advance to high levels of testing much faster than the whole shebang using Prime95. I haven't figured out when to make a transition, though.

2003-09-23, 20:56	#10
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 10001011111₂ Posts	timings on Cunningham numbers I just timed some curves running on a couple of Cunningham numbers on a 1900 MHz Pentium 4 and found something interesting. These curves were run to a stage 1 bound of 11,000,000 and the standard stage 2 bound of 100 times the stage 1 bound. M1001: stage 1, 208 seconds stage 2, 115 seconds P1001: stage 1, 518 seconds stage 2, 204 seconds M2002: stage 1, 310 seconds stage 2, 147 seconds The slowness on P1001 is easily understood to result from the fact that SSE2 instructions are not implemented in the multiplication code for P-numbers. However, the interesting thing is that the time to run a curve on M2002, which is equivalent to running a curve on M1001 and P1001 simultaneously, is only 37% more than the time to run on M1001 alone. I haven't checked, but I suspect that there is probably a similar gain on Athlon and Pentium 3 computers. I should add that I needed to create entries for M2002 in the lowm.txt file in the Prime95 folder, but this was easily done by combining the existing factors for M1001 in lowm.txt and P1001 in lowp.txt. (The files are available for download at http://www.mersenne.org/ecm.htm ) Note that the entries in lowm.txt must be ordered in increasing exponent size, so, for example, the entries for M2002 must come before the entries for M2003, but after entries for M1999, M2000, M2001, etc. Less work has been done on the P-numbers in the Cunningham lists, but the following exponents are those for which both the P-number and the M-number are unfactored. I would suggest to those interested that running curves to stage 1 bounds of 11,000,000 and 44,000,000 on the double exponent number may be an efficient way to work on these unfactored Cunningham numbers. The complete list of exponents n for which Mn and Pn are both unfactored is: 761 787 791 799 805 811 823 827 853 859 863 877 887 893 905 913 923 933 947 949 961 991 1001 1009 1019 1021 1025 1027 1033 1037 1043 1051 1055 1067 1079 1087 1091 1105 1109 1115 1123 1127 1131 1133 1135 1137 1139 1147 1151 1153 1157 1159 1161 1163 1165 1167 1173 1175 1177 1179 1183 1187 1191 1193

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factoring Mersenne numbers	paulunderwood	Miscellaneous Math	18	2017-08-27 14:56
2 holes in bizarre theorem about composite Mersenne Numbers	wildrabbitt	Math	120	2016-09-29 21:52
Highly composite polynomials.	Arkadiusz	Math	5	2012-02-27 14:11
Mersenne primes have highly composite p-1?	ATH	Math	3	2009-06-15 13:11
Factoring with Highly Composite Modulus	mgb	Math	3	2006-09-09 10:35

2003-08-20, 21:37	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	Factoring highly composite Mersenne numbers This thread is sort of a continuation to those started by wblipp on the factors of M5040. The numbers he has been working on have highly composite exponents, and I have been working on similarly composite exponents the past 5 weeks using a different method and Prime95, and wanted to share what I've found. I've been interested in iterated Mersenne numbers M(M(n)) where M(n)=2^n-1 and n is not too large. Will Edgington has a web-page on these numbers for the case where M(n) is a Mersenne prime, but these are tough, and not too many factors are known. On the other hand, if n is composite, M(n) is even more so, and M(M(n)) (I'll just write MMn from now on) is highly composite. These numbers are roughly the size of the Fermat numbers, but in general, easier to factor because they have more factors. However, the method works on any M(n) for a composite n, so I'll describe it using M(30030) as an example. 30030=23571113, so for each proper factor m of 30030, M(m) is a factor of M(30030). Rather than work on just the primitive part of M(30030), which, if I understand correctly, is wblipp's method, I set up the lowm.txt file with all known factors of M(30030), including factors of M(15015), M(10010), M(6006), etc. (In practice, I only put in the factors up to 40 or 50 digits, as larger factors are unllikely to show up in ECM.) It takes quite a bit of work up front, but once done, I can run P-1 and ECM on M30030 and turn up factors of any smaller Mersenne subfactors as well. Since M(30030) has 2^6-1=63 distinct pieces, of which 10 are not yet completely factored, running a curve on M(30030) in effect attempts to find factors of 10 different Mersenne numbers simultaneously. So, for example, I found the following factors running ECM and P-1 on M30030: M3003: 148781787948190413131571457 M4290: 52441211236235251* M5005: 118449316117077011675941481669521 M6006: 766701202212468052531 M10010: 20312320609781201 M10010: 140925959524554569735371 M15015: 1505297798475152441761 M15015: 11329238455344375886321 M30030: 6713804061670210489464481 The asterisks indicate that the primitive part of M4290 is now completely factored, as a 261-digit cofactor was also proven prime. (Unfortunately, M4290 is still not completely factored since M2145 is not, but P2145 is completely factored.) A few points if you decide to do this. 1) You can use Will Edgington's files to find the factors for lowm.txt. Will normally does not list the largest factor of completely factored Mersennes to save space, so you may have to compute this, but if it is over 50 digits, you can probably safely skip it. 2) Will's files do not list repeated factors. For example, M21=7^2127337. One factor of 7 comes because M21 is divisible by M3=7, but the other comes since 21=37. He lists M21 as D (for done), but you have to recognize that there is another 7 to be taken out of the product M21/(M3M7) before you get the final prime factor 337. 3) If you do this for an exponent divisible by 8, you will have to take into account Aurifeullian factorizations. I haven't had to do this, since all M(n) are odd, but you should be aware of this if you try it. Maybe wblipp can tell us how he handles this. 4) When you find a factor, you still do not know to what exponent it corresponds. I usually play around with MAPLE to figure this out, 2&^(30030/x)=1? for what values of x. 5) Occasionally, especially if you try P-1 factoring first, which I recommend especially on larger exponents, you may turn up several factors at once, which shows up as a large composite exponent. When this happens, I use Dario Alpern's java applet to quickly factor the composite into primes. (Thanks, Dario!) Here are the factors I have found recently for iterated Mersenne numbers. In most cases, I ran P-1 and ECM on the full number, but for MM24, I ran a few curves on M69615, since 69615 is a factor of M24, and I can run more curves on M69615 than on MM24=M16777215. For n greater than 26, MMn is too large for Prime95 and I only ran on pieces. factors found: (A couple of these may be already known, but most are new.) MM15 M32767: 1068068525221937 MM16 M21845: 1211325473810854711 M65535: 11176078153580687409841 M65535: 1174653632931498493221732315481 MM18 M3591: 1423477480583686033801 M4161: 3672306633037027038343 M4161: 34415683896971856527721511 M4161: 50025948683707127142710139761032216969116361 M4599: 23762841504942692358991 M9709: 1352358807140765383 M9709: 2779222612409960558896559 M13797: 28696576370397202523719 M29127: 16267633913287 M29127: 5302845396960049 M29127: 1190654334109779234151 M37449: 34257210379744472627001409 M87381: 9772938708077706182408143 M262143: 137047273990488836451289 MM20 M6355: 32133782835946105615711 M13981: 711592027916639 M25575: 45769053349801 M33825: 1579241765314951 M69905: 50129015311 M69905: 49541108644483255361 M69905: 2495793068897706189481 M1048575: 33797174472601 MM21 M42799: 523337729993416956257 MM22 M15709: 1227801105600337 M47127: 75896431183 M47127: 1009531506607987236949561 M1398101: 44703303600503 MM24 M5355: 14454894086094092973322681 M10845: 1838659298945671 M13923: 2403085484872801 M15183: 49158399420079489 M21931: 75084924799115687 M25305: 797500182991 M28679: 37679387929 M28679: 175225535311 M28679: 22169463523201 M36873: 55478611690043041 M46995: 18678820681 M53261: 1381827990583 M61455: 841632124681 M69615: 22658482476631 M69615: 39859832812220636671 M75915: 122438536189831 M86037: 17159907577 M109655: 3171698838742791631 M159783: 1338562269409 M328965: 292120921 M328965: 335072816835121 M430185: 535177230470191 M798915: 4722853131361 M798915: 88547053762441 M798915: 11276411307405271 M1118481: 980956754885017 M1290555: 2119091311 M1864135: 44247108361 M2396745: 242301332521 M3355443: 185629817647 MM25 M1082401: 128667171673 M33554431: 13809930057809 MM26 M24573: 400436693401 M67108863: 54297512617849 MM27 M19173961: 114430199249 MM29 M486737: 52006801325877583 MM32 M196611: 64836016249 M327685: 7605486928751 M327685: 3626169746755001 M3342387: 73488882480103 M5570645: 22327145161 M16843009: 355286431847 M16711935: 645615472921 Any questions, I'll try to answer here in the forum. I think this is a viable way of attacking highly composite Mersenne exponents, and also rewarding in terms of the number of factors turned up. Phil

2003-08-22, 12:17	#2
alpertron Aug 2002 Buenos Aires, Argentina 2526₈ Posts	I think that wblipp's approach is better. Most of the time ECM code is doing modular multiplications. This means that the time needed to process a curve up to some bound is related to the square of the number of digits of the number to factor when you use Montgomery multiplications as in my applet or O(d^1.585) when you use Karatsuba multiplications for large numbers. So if you know the factorization of a number in two or more composites, as in this case, it is faster to do ECM in the factors separately. For example, it is twice as fast to perform ECM for the both numbers M(n) and M(n)+2 than for M(2n) if Montgomery multiplications are used and about 50% faster if Karatsuba multiplication is used.

2003-08-22, 22:52	#3
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	I certainly agree with your heuristics, but you also must keep in mind that Prime95 uses DWT-based multiplication, which takes time on the order of O(nln n) where n is the number of digits in the number. So for large n, doubling the number of digits only slightly more than doubles the amount of time needed for a multiplication. However, since numbers have to be large in order for DWT to be advantageous, you can argue that the multiplication routines used in gmp-ecm might be better for numbers the size of those being factored by wblipp. Still, the Prime95 code is highly optimized and I'm not entirely convinced that its optimizations don't make this method competitive. Consider, in 5 weeks using just two 1600 MHz Pentium 4 computers, I have found 83 new factors, and 55 of these factors have been of Mersenne numbers with four or five digit exponents, i.e., comparable to the exponents being worked on by wblipp. Running 300 curves at B1=50,000 on M30030 took about 5 hours of P4 computer time on one of these computers, and running 700 curves at B1=250,000 took about 2.4 days. (B2=100B1 is the default stage 2 bound.) It would be interesting to see a comparison to the time it would take a comparable machine running this number of curves on the 9 composites contained in M30030, which were originally a C145, C264, C278, C416, C428, C850, C868, C1724, and a C1735. (I am omitting the C177 from M1001 and the C212 from P1001 as these Cunningham numbers had already been searched to a fairly high limit and I did not expect to find any new factors.) The other issue is set-up time, but as a certain amount of set-up can certainly be automated, perhaps it is currently more of an issue than it should be. At any rate, so little work has been done on these Mersenne numbers with composite exponents, both of these methods certainly are proving fruitful. Phil

2003-08-23, 07:58	#4
smh "Sander" Oct 2002 52.345322,5.52471 29·41 Posts	A while ago i did some very limmited speed testing on Prime95 and GMP-ECM 5 On a P4, prime95 turned out to be about 4 times faster on mersenne numbers in stage 1 (Running 1M curves on M959 and M971). Even taking of about 40 digits of known factors of M959 didn't make GMP-ECM faster, actually it was slower than factoring the full number. So you need a much smaller cofactor to make the use of GMP-ECM efficient. On stage 2, prime95 is slightely faster (10%), but taking of that 40 digits of M959 makes that one about 10% faster. I guess on a Athlon or P3 things will be different (maybe stage 2 og GMP-ECM much faster?)

2003-09-06, 14:09	#9
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 651₈ Posts	I think you have to enter the factors explicitly as factors of M1575. Make a new line [code:1]M( 1575 )C: thefactor[/code:1]for each factor.

2003-09-23, 23:31	#11
wblipp "William" May 2003 New Haven 2·7·13² Posts	It isn't clear which circumstances favor Prime95 over ECM. It's especially confusing for a project like ElevenSmooth that has already set up an ECM server and has some numbers tested to much higher levels than other numbers. Issues tilting toward Prime95 are P4 processors, many simultaneous factors, lightly factored numbers. and large numbers. I conducted some timing comparisons to help decide where Prime95 would best fit into the ElevenSmooth project. These comparisons were all made on a P2, so the Prime95 advantage on P4's isn't included in this. The smallest composite in the ElevenSmooth project is the 149 digit factor from the 475 digit M(1575). As expected, ECM was faster for this - by a factor of 4. A fairer comparison would be a cluster of simultaneous numbers, but these are hard to find in the previously worked numbers because the combinable factors tend to be at different ECM levels. The best I could find was a cluster of three numbers in the low 300 digits that were close together. This clustering and lesser factoring helped Prime95, but ECM was still 2 time faster. A much larger cluster comes from the three largest composites from M(665280). These range from 10,000 to 40,000 digits. Prime95 was five times faster on these. Clearly Prime95 is the better tool for working on the largest exponents. The ElevenSmooth project was at a transition point of having put all the factors of M(665280) into the ECM server, and ready to begin on the additional exponents of M(3326400) - those exponents that are multiples of 25. Clearly the right way to start the multiples of 25 was to use Prime95. We've just finished the first stage at B1=2000, and we found 40 factors - see the other thread for details, but this compares to a total of 51 factors previously found for the M(665280) subset. Longer term it probably makes sense to split some of the factors out into the ECM server, where they can advance to high levels of testing much faster than the whole shebang using Prime95. I haven't figured out when to make a transition, though.