20030820, 21:37  #1 
"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^n1 and n is not too large. Will Edgington has a webpage 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 P1 and ECM on M30030 and turn up factors of any smaller Mersenne subfactors as well. Since M(30030) has 2^61=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 P1 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 261digit 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 P1 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 P1 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 
20030822, 12:17  #2 
Aug 2002
Buenos Aires, Argentina
2557_{8} 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. 
20030822, 22:52  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
45F_{16} Posts 
I certainly agree with your heuristics, but you also must keep in mind that Prime95 uses DWTbased 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 gmpecm 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 setup time, but as a certain amount of setup 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 
20030823, 07:58  #4 
"Sander"
Oct 2002
52.345322,5.52471
10010100101_{2} Posts 
A while ago i did some very limmited speed testing on Prime95 and GMPECM 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 GMPECM faster, actually it was slower than factoring the full number. So you need a much smaller cofactor to make the use of GMPECM 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 GMPECM much faster?) 
20030901, 19:15  #5  
"William"
May 2003
New Haven
23·103 Posts 
Re: Factoring highly composite Mersenne numbers
Quote:
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 P1 and ECM testing, or do you recommend editting the worktodo.ini file? 

20030901, 20:52  #6  
Aug 2002
2^{2}·3·17·41 Posts 
2  Yes...
3  I use the worktodo.ini file... Quote:


20030902, 23:22  #7  
"William"
May 2003
New Haven
23·103 Posts 
Re: Factoring highly composite Mersenne numbers
Quote:
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?) 

20030906, 04:09  #8  
"William"
May 2003
New Haven
23×103 Posts 
Re: Factoring highly composite Mersenne numbers
Quote:
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? 

20030906, 14:09  #9 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
425_{10} 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. 
20030923, 20:56  #10 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 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 Pnumbers. 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 Pnumbers in the Cunningham lists, but the following exponents are those for which both the Pnumber and the Mnumber 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 
20030923, 23:31  #11 
"William"
May 2003
New Haven
23·103 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Highly composite polynomials.  Arkadiusz  Math  5  20120227 14:11 
Mersenne primes have highly composite p1?  ATH  Math  3  20090615 13:11 
Factoring with Highly Composite Modulus  mgb  Math  3  20060909 10:35 