Help wanted, Mersenne base Cunningham numbers

[kosta]

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.

[LaurV]

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?

[Dubslow]

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.)

[Batalov]

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.

# For x=M8,
4950036370987531796596777020435431752821658735009564665203032637182311299258729058872170618265983042169789410985851232822128958988972946232939020745222679656170411937888556774248091592015827689480701 
from polcyclo(35)
 
1952329202661866602684979956787714136482531226833055496710056683028658100012799836257527350037275596384189190550132825485135466639172655355292471161449599261594798638028373903096628381188057821540414523320973594741 
from polcyclo(70)
 
46369274539511602716742354076173217450608724440380513760194223916069324192902767004986499586652143885268600362124441387096750490754062590523804767119953375702817305548423829662920946858608012639268981789032289310770689470160041527105051397166080657438847761837831268693089157439654371670093018666831058845711106427004237789279071968316503094310064329829081013746165289238329246860439507543246420660935942738032299370416234782261 
from polcyclo(210)
 
1143123785300137827229113733976321513214673104741914799647432606327453025175451712163585875922192281746654565288633260510004455610284067612834163154108362636721077385987372903016222032787696363549385834287363229105082627641710332824549804735135998050591530318533650450966428851669318317267992793009771125769038568017375825042228156692874332732449902003315448161794577417845604943681444094729223414462740834160216471259255879814752790099241 
from polcyclo(105)

[Batalov]

Here are the polys:

n: 16314315482963226490821946080971549450706222359508882207070502298741881754665051765380282665291356409074285196429704092132126707585162244439000837928127809542351956738323750370087594623357586179416038045807359853
Y1: 2305843009213693951
Y0: -5316911983139663487003542222693990402
c6: 1
c5: -1
c4: -6
c3: 6
c2: 8
c1: -8
c0: 1
type: snfs
skew: 1

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

[Batalov]

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.

[Dubslow]

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.)

# 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.

[kosta]

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

[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.

[c10ck3r]

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.

[Batalov]

Well, because this is a snfs-221, 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, 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)