Factoring humongous Cunningham numbers

[fivemack]

10-7.191 S191 (152) [14e/27lp/2^23sp] (1048428s + 336s + 11837s@4CPU + 1478s/2)
Fri Sep 11 20:08:31 2009 prp42 factor: 602042088775639986918297776645429449546619
Fri Sep 11 20:08:31 2009 prp110 factor: 33929634886978114141291477425365580390751852643524199226349853412013173286258912284088108701389099986638761717

(a million seconds is nearly 2*p45, and the factor's only a p42)

[Joe O]

Originally Posted by fivemack

10-7.191 S191 (152) [14e/27lp/2^23sp] (1048428s + 336s + 11837s@4CPU + 1478s/2)
Fri Sep 11 20:08:31 2009 prp42 factor: 602042088775639986918297776645429449546619
Fri Sep 11 20:08:31 2009 prp110 factor: 33929634886978114141291477425365580390751852643524199226349853412013173286258912284088108701389099986638761717

(a million seconds is nearly 2*p45, and the factor's only a p42)

Are you saying that
1) not enough ECM was run on this number?
2) the ECM program is faulty?
3) something else?

[fivemack]

I tend to use 'ECM miss' to mean 'if I'd run ECM instead of snfs, I would have found the factor more quickly'; I appreciate this is probably not the normal use of the term.

[R.D. Silverman]

Originally Posted by fivemack

I tend to use 'ECM miss' to mean 'if I'd run ECM instead of snfs, I would have found the factor more quickly'; I appreciate this is probably not the normal use of the term.

No, I would say that this is the accepted usage of "ECM miss".

[Andi47]

Originally Posted by Andi47

Do I get this right, a difficulty-193-SNFS would take approx. as long as a 193*0.69 = 133-digit GNFS and thus would be in range for home computing?

Seems that this one didn't have much ECM (unfortunately, the reservation page doesn't give information about the amount of ECM done on each number).

Yesterday, I just thought to give it a try and run a bunch of curves on it overnight, and...

Run 110 out of 500:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=4183249465
Step 1 took 237281ms
Step 2 took 62016ms
********** Factor found in step 2: 2349783051111976239049347232722196704029
Found probable prime factor of 40 digits: 2349783051111976239049347232722196704029
Probable prime cofactor 1541091246548990353689435982710386631762710119356152870973958183688458251235091483146681989184564163537618914925796259 has 118 digits

[xilman]

Originally Posted by Andi47

Seems that this one didn't have much ECM (unfortunately, the reservation page doesn't give information about the amount of ECM done on each number).

Yesterday, I just thought to give it a try and run a bunch of curves on it overnight, and...

Run 110 out of 500:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=4183249465
Step 1 took 237281ms
Step 2 took 62016ms
********** Factor found in step 2: 2349783051111976239049347232722196704029
Found probable prime factor of 40 digits: 2349783051111976239049347232722196704029
Probable prime cofactor 1541091246548990353689435982710386631762710119356152870973958183688458251235091483146681989184564163537618914925796259 has 118 digits

All the numbers in the ECMnet server have essentially the same amount of work done on them, that being the allocation strategy set up.

At the moment, the server is about half-way through handing out curves with B1=3M, so the expected size of factors to be found will be around 40 digits or perhaps a little less.

That the p40 factor above has not yet been found by the ECMnet clients is not at all surprising.


Paul

[Joe O]

Originally Posted by fivemack

I tend to use 'ECM miss' to mean 'if I'd run ECM instead of snfs, I would have found the factor more quickly'; I appreciate this is probably not the normal use of the term.

But even at 2*P45 there would be a ~14% probability of missing a 45 digit factor. It might have taken a lot more curves, and cpu time.

[yoyo]

Should I run some ECM curves via yoyo@home on it?
yoyo

[unconnected]

7^299-6^299
c183=p43*p140
p43=1895196682008094522046817009226083917957561

by ECM

[Yamato]

Some more factors...

Run 172 out of 1000:
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=664469849
Step 1 took 11192ms
********** Factor found in step 1: 16329409528242736979240605668734636153
Found probable prime factor of 38 digits: 16329409528242736979240605668734636153
Probable prime cofactor (((((9^203-8^203)/407353462746867001)/298093771407041)/6233803301928460803553)/4555386192335572300559213161)/16329409528242736979240605668734636153 has 75 digits

Run 27 out of 1000:
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=2682735469
Step 1 took 20494ms
Step 2 took 8464ms
********** Factor found in step 2: 524451880982120622418669944269190199223
Found probable prime factor of 39 digits: 524451880982120622418669944269190199223
Probable prime cofactor ((8^257+5^257)/(13*5746950733*38434462212856815594943*1258221908128778009146226401))/524451880982120622418669944269190199223 has 133 digits

[fivemack]

Originally Posted by yoyo

Should I run some ECM curves via yoyo@home on it?
yoyo

There's already an ecmnet server (port 8194 on the machine 83.143.57.194) set up with these numbers in; I think to some extent they're intended as a gentle introduction for the NFS methods, and throwing CPU-years of ECM at them might be inappropriate.