mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2003-08-20, 21:37   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default 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=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
philmoore is offline   Reply With Quote
Old 2003-08-22, 12:17   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

132510 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2003-08-22, 22:52   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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
philmoore is offline   Reply With Quote
Old 2003-08-23, 07:58   #4
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

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?)
smh is offline   Reply With Quote
Old 2003-09-01, 19:15   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

93616 Posts
Default Re: Factoring highly composite Mersenne numbers

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?
wblipp is offline   Reply With Quote
Old 2003-09-01, 20:52   #6
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2·3·5·257 Posts
Default

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.
Xyzzy is offline   Reply With Quote
Old 2003-09-02, 23:22   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44668 Posts
Default Re: Factoring highly composite Mersenne numbers

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 is offline   Reply With Quote
Old 2003-09-06, 04:09   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default Re: Factoring highly composite Mersenne numbers

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?
wblipp is offline   Reply With Quote
Old 2003-09-06, 14:09   #9
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

6508 Posts
Default

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.
patrik is offline   Reply With Quote
Old 2003-09-23, 20:56   #10
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2003-09-23, 23:31   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 00:44.

Wed Sep 30 00:44:08 UTC 2020 up 19 days, 21:55, 0 users, load averages: 1.70, 1.85, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.