Factoring humongous Cunningham numbers

[pinhodecarlos]

Input number is 176648521095254757695831572017874418458831244642790650826091193431673766367336763489498160619901783806447404240317078462752799029 (129 digits)
Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=1:308916830
Step 1 took 65926ms
Step 2 took 27644ms
********** Factor found in step 2: 1280728140217088011740794602021286161592377441
Found prime factor of 46 digits: 1280728140217088011740794602021286161592377441
Prime cofactor 137928195335281849907271729444618846169208007815817801433599225868254496324250851669 has 84 digits

[xilman]

Originally Posted by pinhodecarlos

Input number is 176648521095254757695831572017874418458831244642790650826091193431673766367336763489498160619901783806447404240317078462752799029 (129 digits)
Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=1:308916830
Step 1 took 65926ms
Step 2 took 27644ms
********** Factor found in step 2: 1280728140217088011740794602021286161592377441
Found prime factor of 46 digits: 1280728140217088011740794602021286161592377441
Prime cofactor 137928195335281849907271729444618846169208007815817801433599225868254496324250851669 has 84 digits

Thanks. Good find by ECM.

Paul

[Batalov]

Here are the remaining super-easy snfs candidates for anyone to grab:

#____the expos are divisible by 15: use quartic____
#Expression     Length  Starts  Difficulty 
11 285 + 10 285 139     5005... 158.2
11 285 - 5 285  140     1832... 158.2
11 285 - 6 285  117     2320... 158.2
11 285 + 6 285  135     6794... 158.2
9 315 - 2 315   126     1819... 160.3
9 315 + 5 315   125     7408... 160.3
5 435 + 2 435   157     2847... 162.1
7 360 + 2 360   158     9001... 162.2
7 360 + 5 360   137     1191... 162.2
12 285 - 11 285 147     9019... 164.0
12 285 + 11 285 149     2677... 164.0
#____the expos are divisible by 21: use sextic____
7 336 + 5 336   145     5369... 162.2
7 336 + 6 336   141     3195... 162.2
11 273 - 10 273 140     5600... 162.4
11 273 + 10 273 145     3526... 162.4
11 273 - 3 273  135     3394... 162.4
11 273 + 5 273  128     2484... 162.4
11 273 - 5 273  151     1510... 162.4
11 273 + 6 273  142     5344... 162.4
11 273 + 9 273  125     4620... 162.4
3 609 - 2 609   149     8354... 166.0
3 609 + 2 609   151     5277... 166.0
6 378 + 5 378   143     8121... 168.0
7 357 + 5 357   159     4439... 172.4
11 294 + 2 294  124     1461... 174.9
11 294 + 3 294  140     2949... 174.9
11 294 + 9 294  114     8709... 174.9 /--gnfs!
5 441 - 2 441   164     6161... 176.1
5 441 + 3 441   152     6398... 176.1

[debrouxl]

The site is not reachable for me at the moment, from two very different network environments. The Web server accepts connections, but doesn't reply to HTTP requests

Reviving an ECMNet server for HCN composites would probably speed up splitting 40-50 digit prime factors.

[frmky]

Input number is 135208777652707551627613394323172349287658234884006214941830419038629271216360971380190458698241219665584896965795899 (117 digits)
Using B1=11000000, B2=5714965630, sigma=3:3291808790-3:3291809621 (832 curves)
GPU: Block: 16x32x1 Grid: 26x1x1 (832 parallel curves)
Computing 832 Step 1 took 70619ms of CPU time / 1919508ms of GPU time
GPU: factor 1259183377997512211834207021579593490689 found in Step 2 with curve 809 (-sigma 3:3291809599)
Computing 832 Step 2 on CPU took 1562272ms
********** Factor found in step 2: 1259183377997512211834207021579593490689
Found prime factor of 40 digits: 1259183377997512211834207021579593490689
Prime cofactor 107378146833331757743843198866359402606798797253252448208276600932366296728891 has 78 digits

[ET_]

Originally Posted by frmky

Input number is 135208777652707551627613394323172349287658234884006214941830419038629271216360971380190458698241219665584896965795899 (117 digits)
Using B1=11000000, B2=5714965630, sigma=3:3291808790-3:3291809621 (832 curves)
GPU: Block: 16x32x1 Grid: 26x1x1 (832 parallel curves)
Computing 832 Step 1 took 70619ms of CPU time / 1919508ms of GPU time
GPU: factor 1259183377997512211834207021579593490689 found in Step 2 with curve 809 (-sigma 3:3291809599)
Computing 832 Step 2 on CPU took 1562272ms
********** Factor found in step 2: 1259183377997512211834207021579593490689
Found prime factor of 40 digits: 1259183377997512211834207021579593490689
Prime cofactor 107378146833331757743843198866359402606798797253252448208276600932366296728891 has 78 digits

I didn't know that the bug that prevented a factor from Step 2 to be discovered by a GPU had been squashed!
What SVN should I download?

Luigi

[xilman]

Originally Posted by ET_

I didn't know that the bug that prevented a factor from Step 2 to be discovered by a GPU had been squashed!
What SVN should I download?

Luigi

The latest, of course.

There was great rejoicing on the ecm-discuss@lists.gforge.inria.fr list (by me, if no-one else) when the other Paul found the bug and corrected it.

Paul

[jyb]

Originally Posted by Batalov

Here are the remaining super-easy snfs candidates for anyone to grab:

#____the expos are divisible by 15: use quartic____

[snip]

#____the expos are divisible by 21: use sextic____

[snip]

In case anyone needs help with generating the correct polynomials for these, you can use the "phi" program. Latest version can be found here.

[wombatman]

Originally Posted by ET_

I didn't know that the bug that prevented a factor from Step 2 to be discovered by a GPU had been squashed!
What SVN should I download?

Luigi

Agreed! That is very exciting!

[Batalov]

Originally Posted by debrouxl

The site is not reachable for me at the moment, from two very different network environments. The Web server accepts connections, but doesn't reply to HTTP requests ...

The site still appears down (was then and still is)

[bsquared]

Originally Posted by frmky

Input number is 135208777652707551627613394323172349287658234884006214941830419038629271216360971380190458698241219665584896965795899 (117 digits)
Using B1=11000000, B2=5714965630, sigma=3:3291808790-3:3291809621 (832 curves)
GPU: Block: 16x32x1 Grid: 26x1x1 (832 parallel curves)
Computing 832 Step 1 took 70619ms of CPU time / 1919508ms of GPU time
GPU: factor 1259183377997512211834207021579593490689 found in Step 2 with curve 809 (-sigma 3:3291809599)
Computing 832 Step 2 on CPU took 1562272ms
********** Factor found in step 2: 1259183377997512211834207021579593490689
Found prime factor of 40 digits: 1259183377997512211834207021579593490689
Prime cofactor 107378146833331757743843198866359402606798797253252448208276600932366296728891 has 78 digits

Nice!
Out of curiosity, can you say what NVidia card was used to do this? Also, I'm ignorant of how the program works... does the 70-some seconds of CPU usage occur concurrent to the GPU time? i.e., does the GPU operation consume some CPU cycles as well? Or it is up-front CPU initialization or something? I assume the program stops in step 2 after a factor is found, so that the timing there is for 809 curves instead of 832?