mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-01-10, 12:59   #1
kosta
 
Jan 2013

708 Posts
Default 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.
kosta is offline   Reply With Quote
Old 2013-01-11, 02:43   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×11×157 Posts
Default

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?
LaurV is offline   Reply With Quote
Old 2013-01-11, 02:54   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

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 2013-01-11 at 03:00
Dubslow is offline   Reply With Quote
Old 2013-01-11, 03:23   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

31×293 Posts
Default

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)
Batalov is offline   Reply With Quote
Old 2013-01-11, 03:35   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

31·293 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2013-01-11, 04:01   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

31·293 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2013-01-11, 07:31   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.784174e-11 alpha -5.582809 e 4.519e-10 rroots 5
skew: 24038.95
c0: 601368913675808451774859659
c1: 45707493188864326845371
c2: -5951954845371833633
c3: -202526268211707
c4: 12499019278
c5: 114072
Y0: -19994885629035903755390
Y1: 2518574512409
I'm done for now though.
Dubslow is offline   Reply With Quote
Old 2013-01-12, 21:18   #8
kosta
 
Jan 2013

23×7 Posts
Default 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
kosta is offline   Reply With Quote
Old 2013-01-12, 21:26   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

215738 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2013-01-13, 00:02   #10
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
c10ck3r is offline   Reply With Quote
Old 2013-01-13, 02:11   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

237B16 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Numbers wanted for OEIS sequences sean Factoring 148 2020-06-29 14:19
New phi for homogeneous Cunningham numbers wpolly Factoring 26 2016-07-29 04:34
Don't know how to work on Cunningham numbers. jasong GMP-ECM 6 2006-06-30 08:51
Doing Cunningham numbers but messed up. jasong Factoring 1 2006-04-03 17:18
Cunningham Base-2 Half Server 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

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.