mersenneforum.org Help wanted, Mersenne base Cunningham numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2013-01-10, 12:59 #1 kosta   Jan 2013 708 Posts Help wanted, Mersenne base Cunningham numbers I would like to request help to factor numbers of the form M^k-1, 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^31-1 AND k=32 and k=60 and k=42 for M9=2^61-1 These currently usually just one composite factor, of 100-200 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.
 2013-01-11, 02:43 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 5×11×157 Posts There is only one composite number (of 199 digits) in the range for those two k's, all the rest are 200-500 digits composites. Are you talking about that one, or in general?
 2013-01-11, 02:54 #3 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2013-01-11, 03:23 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 31×293 Posts Crosspost. Anyway - You need to run over cyclotomic factorizations. For k=60 and M9=2^61-1, the only cofactor left is for (2^61-1)^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 snfs-221 jobs with nice sextics. No gnfs-191 here. Code: # For x=M8, 4950036370987531796596777020435431752821658735009564665203032637182311299258729058872170618265983042169789410985851232822128958988972946232939020745222679656170411937888556774248091592015827689480701 from polcyclo(35) 1952329202661866602684979956787714136482531226833055496710056683028658100012799836257527350037275596384189190550132825485135466639172655355292471161449599261594798638028373903096628381188057821540414523320973594741 from polcyclo(70) 46369274539511602716742354076173217450608724440380513760194223916069324192902767004986499586652143885268600362124441387096750490754062590523804767119953375702817305548423829662920946858608012639268981789032289310770689470160041527105051397166080657438847761837831268693089157439654371670093018666831058845711106427004237789279071968316503094310064329829081013746165289238329246860439507543246420660935942738032299370416234782261 from polcyclo(210) 1143123785300137827229113733976321513214673104741914799647432606327453025175451712163585875922192281746654565288633260510004455610284067612834163154108362636721077385987372903016222032787696363549385834287363229105082627641710332824549804735135998050591530318533650450966428851669318317267992793009771125769038568017375825042228156692874332732449902003315448161794577417845604943681444094729223414462740834160216471259255879814752790099241 from polcyclo(105)
 2013-01-11, 03:35 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 31·293 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: 313983163622811484129671100678665946954449850208757428672195940996255448447954034120094393508180713469117748283905862111228586727450949749235456697912247587405643791440611952400806156681788105160997 Y1: 2305843009213693951 Y0: -5316911983139663487003542222693990402 c6: 1 c5: 1 c4: -6 c3: -6 c2: 8 c1: 8 c0: 1 type: snfs skew: 1 # t=x+1/x ; polcyclo(42)/x^6-(t^6+t^5-6*t^4-6*t^3+8*t^2+8*t+1) => 0 Last fiddled with by Batalov on 2013-01-18 at 22:09 Reason: The smaller one is ECMd
 2013-01-11, 04:01 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 31·293 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 Argh. No snfs for this one. 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 2013-01-11 at 04:12 Reason: /code/ tags added
 2013-01-11, 07:31 #7 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2013-01-12, 21:18 #8 kosta   Jan 2013 23×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^32-1 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^60-1 is now CF. K
 2013-01-12, 21:26 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 215738 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.
2013-01-13, 00:02   #10
c10ck3r

Aug 2010
Kansas

547 Posts

Quote:
 Originally Posted by Batalov 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.
Running 890 curves at 1e6.

 2013-01-13, 02:11 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 237B16 Posts Well, because this is a snfs-221, it would be prudent to eliminate factors up to 2/9 (or 2/8th) of the size before actually running SNFS. So, that's about 50- or if we are generous, 55-digit level. I am running some 43e6 curves on the three smallest composites (this corresponds to the 50-digit 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 11-12 curves per hour on 1 relatively modern cpu) Last fiddled with by Batalov on 2013-01-13 at 02:14

 Similar Threads Thread Thread Starter Forum Replies Last Post sean Factoring 148 2020-06-29 14:19 wpolly Factoring 26 2016-07-29 04:34 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 wblipp Factoring 10 2004-04-21 02:15

All times are UTC. The time now is 10:53.

Tue Aug 11 10:53:16 UTC 2020 up 25 days, 6:40, 1 user, load averages: 2.77, 2.38, 2.15