20130110, 12:59  #1 
Jan 2013
111000_{2} Posts 
Help wanted, Mersenne base Cunningham numbers
I would like to request help to factor numbers of the form M^k1, where M is a Mersenne prime. factordb has most up to date results on this, and this is where i submit whatever factors i find. The factorizations are of interest for construction of random number generators with large moduli, if there is interest i can explain in more detail. Currently, I am most interested in M8 and M9. I choose k so that the algebraic factorizations are most numerous and bring down the number of digits remaining to factor as much as possible. Namely, of interest are
k=210 and k=168 for M8=2^311 AND k=32 and k=60 and k=42 for M9=2^611 These currently usually just one composite factor, of 100200 digits, and I am running ECM on them with whatever i got, which is not much. Few dozen curves with 1E6. Help would be greatly appreciated. 
20130111, 02:43  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
9,787 Posts 
There is only one composite number (of 199 digits) in the range for those two k's, all the rest are 200500 digits composites. Are you talking about that one, or in general?

20130111, 02:54  #3 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
The other three k have rather smaller co factors. For k=60, there's a C117 that should last no more than a day against my yafu+Intel. Consider that a reservation. (The next smallest is a feasible C191; if it stands ECM, it would be an interesting GNFS job, if fivemack were willing to post process.) (PS Perhaps a mod should move this to its own thread.)
Last fiddled with by Dubslow on 20130111 at 03:00 
20130111, 03:23  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
17×563 Posts 
Crosspost. Anyway 
You need to run over cyclotomic factorizations. For k=60 and M9=2^611, the only cofactor left is for (2^611)^10+1, a c117, a very easy gnfs. For x=M9, k=42, both composite cofactors are from polcyclo(21) and polcyclo(42) and would be moderate snfs221 jobs with nice sextics. No gnfs191 here. Code:
# For x=M8, 4950036370987531796596777020435431752821658735009564665203032637182311299258729058872170618265983042169789410985851232822128958988972946232939020745222679656170411937888556774248091592015827689480701 from polcyclo(35) 1952329202661866602684979956787714136482531226833055496710056683028658100012799836257527350037275596384189190550132825485135466639172655355292471161449599261594798638028373903096628381188057821540414523320973594741 from polcyclo(70) 46369274539511602716742354076173217450608724440380513760194223916069324192902767004986499586652143885268600362124441387096750490754062590523804767119953375702817305548423829662920946858608012639268981789032289310770689470160041527105051397166080657438847761837831268693089157439654371670093018666831058845711106427004237789279071968316503094310064329829081013746165289238329246860439507543246420660935942738032299370416234782261 from polcyclo(210) 1143123785300137827229113733976321513214673104741914799647432606327453025175451712163585875922192281746654565288633260510004455610284067612834163154108362636721077385987372903016222032787696363549385834287363229105082627641710332824549804735135998050591530318533650450966428851669318317267992793009771125769038568017375825042228156692874332732449902003315448161794577417845604943681444094729223414462740834160216471259255879814752790099241 from polcyclo(105) 
20130111, 03:35  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
17·563 Posts 
Here are the polys:
Code:
n: 16314315482963226490821946080971549450706222359508882207070502298741881754665051765380282665291356409074285196429704092132126707585162244439000837928127809542351956738323750370087594623357586179416038045807359853 Y1: 2305843009213693951 Y0: 5316911983139663487003542222693990402 c6: 1 c5: 1 c4: 6 c3: 6 c2: 8 c1: 8 c0: 1 type: snfs skew: 1 Code:
n: Last fiddled with by Batalov on 20130118 at 22:09 Reason: The smaller one is ECMd 
20130111, 04:01  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010101100011_{2} Posts 
Code:
Input number is 313983163622811484129671100678665946954449850208757428672195940996255448447954034120094393508180713469117748283905862111228586727450949749235456697912247587405643791440611952400806156681788105160997 (198 digits) Using B1=2000000, B2=2853999340, polynomial Dickson(6), sigma=1023729719 Step 1 took 10520ms Step 2 took 5069ms ********** Factor found in step 2: 66300970434526259861746960147 Found probable prime factor of 29 digits: 66300970434526259861746960147 Probable prime cofactor 4735725006210536730416737200594906784559874698023341635364616070767780355545832399453519129364856632375912690185120871263991071662743312333352950403500083391533087960551 has 169 digits There's still a meaty c212 : diff.221. Good ratio. If I were you, I'd grab it before Bill gets here. Last fiddled with by Batalov on 20130111 at 04:12 Reason: /code/ tags added 
20130111, 07:31  #7 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
That C117 had a P33  I probly shoulda done some ECM first. Oh well, it wasn't too huge a miss.
(Besides, in 30 mins of GPU poly select, I got an amazing poly.) Code:
# norm 3.784174e11 alpha 5.582809 e 4.519e10 rroots 5 skew: 24038.95 c0: 601368913675808451774859659 c1: 45707493188864326845371 c2: 5951954845371833633 c3: 202526268211707 c4: 12499019278 c5: 114072 Y0: 19994885629035903755390 Y1: 2518574512409 
20130112, 21:18  #8 
Jan 2013
2^{3}×7 Posts 
thanks!
Thanks everyone who is helping with these Mersenne base Cunningham numbers. (Is this a good name for them?)
many of the factors have not been very much attacked with ecm, but the c191, which is the remaining factor of M9^321 is at http://factordb.com/index.php?id=1100000000572386673 is a hard one, so far few thousand curves at 1E7 did not crack it. As far as my application is concerned, I am fully happy for now, as M9^601 is now CF. K 
20130112, 21:26  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010101100011_{2} Posts 
I've run ~1100 11e6 curves on each of the eight composites. Some small factors easily fell off of the c4xx numbers.
The c212 cofactor can be done by someone on a home computer (it will need some more ECM, though), the others are harder. I'll split this into another thread. 
20130113, 00:02  #10  
Aug 2010
Kansas
547 Posts 
Quote:


20130113, 02:11  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
17·563 Posts 
Well, because this is a snfs221, it would be prudent to eliminate factors up to 2/9 (or 2/8^{th}) of the size before actually running SNFS. So, that's about 50 or if we are generous, 55digit level. I am running some 43e6 curves on the three smallest composites (this corresponds to the 50digit level).
There's a very little chance that a factor will be found with 1e6 (not totally impossible, but very low). The 3e6 was already run (2350 curves), many 11e6 curves were run, so now 7550 curves with 43e6 need to be collected (from all volunteers, who could post there number of curves here) and then someone with clear conscience could go for a SNFS job. P.S. Of course, the 43e6 curves are slow, but that's the only reasonable thing to do. Sample timings are: Step 1 took 260,296ms Step 2 took 76,713ms (i.e. maybe 1112 curves per hour on 1 relatively modern cpu) Last fiddled with by Batalov on 20130113 at 02:14 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Numbers wanted for OEIS sequences  sean  Factoring  148  20200629 14:19 
New phi for homogeneous Cunningham numbers  wpolly  Factoring  26  20160729 04:34 
Don't know how to work on Cunningham numbers.  jasong  GMPECM  6  20060630 08:51 
Doing Cunningham numbers but messed up.  jasong  Factoring  1  20060403 17:18 
Cunningham Base2 Half Server  wblipp  Factoring  10  20040421 02:15 