Factoring humongous Cunningham numbers

[frmky]

Originally Posted by bsquared

For grins I dusted off this code to see if it still worked and as a comparison (hence all the questions above).

BTW, if you want another data point, I can try it on a Phi SE10P. I run the large NFS@Home postprocessing on the TACC Stampede cluster, and most of those nodes have one.

[xilman]

Originally Posted by Batalov

Yep, it is up!

... But no, it is not working: the UPDATE.txt file is empty!

The site is still down, so here's UPDATE.txt file. There are now 1744 composites remaining.

Changes to files from 1 April 2016

Table	n	Old	New														Finder			Method	Date
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3+2	588	C161	375185290692365105486982184469730438633108657100937918621075680968049.	P92					S Batalov	SNFS	2016-04-01
4-3	435	C120	1459017879468905078299839071484733623490504749961.	P72							S Batalov	SNFS	2016-04-01
7+2	301	C106	2434210959900888334996422435526791766751.	P67								S Batalov	SNFS	2016-04-01
8+7	300	C140	66822113400011951652618283171640529391303131821475339773509674787201.	P72					S Batalov	SNFS	2016-04-01
9+5	300	C143	1770153476250997867904335014712803068489655501821605214372801.	P83						S Batalov	SNFS	2016-04-01
9+7	294	C161	111362843254006675884926399795583141489289.	C120								S Batalov	SNFS	2016-04-01
9+7	294	C120	38269860142250842386341778092452625454997475391049.	P70							S Batalov	SNFS	2016-04-01
11+2	243	C164	86967232532439038472096282770133426069069784573.	P117							S Batalov	SNFS	2016-04-02
6+5	316	C177	20206957651913041022106918338431611081608753047535017044690679163933015220179833.	P98			R Dickerson	SNFS	2016-04-03
11-9	255	C118	5352206269748569346687694656502545328991.	P78								S Batalov	SNFS	2016-04-04
9-2	273	C134	2567864246830347665051940878924517506979188352260377823524645682239.	P68					S Batalov	SNFS	2016-04-04
9+7	285	C135	1956858323732285953001536087227128710840535403586621.	P84							S Batalov	SNFS	2016-04-04
11+7	270	C137	8058350931889948260760528329927764767879607469611139901.	P82						S Batalov	SNFS	2016-04-04
11+4	252	C129	25757491789290798358520026686236018799121.	P88								S Batalov	SNFS	2016-04-04
11+4	255	C129	284772344365244251261256081350225638533526751.	P85								S Batalov	SNFS	2016-04-04
11-5	255	C121	318809813180669003684192756177719421375308974898682911.	P67							S Batalov	SNFS	2016-04-04
9+8	285	C135	6334096558478416340094110805107869168424020077871332463701571.	P74						S Batalov	SNFS	2016-04-05
11+3	270	C122	12871929468338567317141161793446373670974495437252181.	P70							S Batalov	SNFS	2016-04-05
10-7	273	C130	3248440692858028149655224720503831494397806704018471979597597.	P70						S Batalov	SNFS	2016-04-05
6+5	357	C122	189980889421744620414249883283734945422120037.	P78								S Batalov	SNFS	2016-04-05
4-3	409	C196	37289909580309862111697012978469498997530066231388984708324720746304706221428537956177353.	P107		R Dickerson	SNFS	2016-04-05
4-3	429	C129	1280728140217088011740794602021286161592377441.	P84								C Pinho		ECM	2016-04-05
11-7	267	C117	1259183377997512211834207021579593490689.	P78								L Morelli	ECM	2016-04-06
11+8	289	C278	47710925766827777230325693915103491788429.	C237								S Batalov	SNFS	2016-04-06
5-4	397	C278	2647603938037522660530176148819684677321.	C239								S Batalov	SNFS	2016-04-06
6+5	383	C284	125828096035824850471308490303855554743239305664987.	P234							S Batalov	SNFS	2016-04-06
5+4	420	C128	66460869807968734003935731357851018870844729984641.	P78							S Batalov	SNFS	2016-04-06
5+4	369	C168	55893163111835616005333061683430078736591894032738127.	P116							S Batalov	SNFS	2016-04-07
6+5	327	C169	18078640871217063613768282633683096905406548338399.	C119							S Batalov	SNFS	2016-04-07
6+5	327	C119	68554020027365804512020110781612045026538806914117.	P70							S Batalov	SNFS	2016-04-07
6+5	375	C126	9178554441826506767299480752609503652183873566505751.	P74							S Batalov	SNFS	2016-04-07
7+2	345	C134	3253376854693368240595609152839805684953214556362500226451782151.	P70					S Batalov	SNFS	2016-04-07
7+4	345	C127	449778848948431711762659589681622694139296018854127990427351.	P68						S Batalov	SNFS	2016-04-07
7-6	345	C123	174487038074027810853266480612839879502499451.	P78								S Batalov	SNFS	2016-04-07
9+5	267	C169	7416625264251830034792477924212399848617909093691282668978289.	P108						S Batalov	SNFS	2016-04-07

No idea when the web site will be up again.

[bsquared]

Originally Posted by WraithX

The 70 seconds on the CPU is the computation of the "batch product": the product of all primes, and prime powers, up to B1. This happens before any work is done on the GPU. Once the batch product, called s in the code, is computed, the code loops over each bit in s and computes x curves (in this case = 32*26) in parallel on the GPU.

The way gpu-ecm is currently configured, it will try to find all factors that it can. ie, it actually does search all 832 curves for factors. I'll talk with PaulZ about possibly recognizing the -one option for gpu-ecm so that the program will stop as soon as it knows it has found a factor.

Also, frmky, based on "Grid: 26x1x1", are you running these "half-sized" curves on a GTX 970?

Originally Posted by frmky

Tesla K20c.
Edit: And don't use that run for timing. That wasn't the only program running on the GPU. For timing purposes, stage 1 on 832 curves on a <= 506-bit number at B1=11e6 take 1640 seconds, or 1.97 s/curve.

Thanks for the info!

Originally Posted by frmky

BTW, if you want another data point, I can try it on a Phi SE10P. I run the large NFS@Home postprocessing on the TACC Stampede cluster, and most of those nodes have one.

And thanks for the offer, that's a nice card. I will have to pass for now, until I can get more organized.

[xilman]

Originally Posted by xilman

No idea when the web site will be up again.

Tech support mailed to say they've restarted Apache. Stuff seems to be visible again now.


Paul

[jyb]

Originally Posted by xilman

...here's UPDATE.txt file. There are now 1744 composites remaining.

Changes to files from 1 April 2016

Table	n	Old	New														Finder			Method	Date
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6+5	316	C177	20206957651913041022106918338431611081608753047535017044690679163933015220179833.	P98			R Dickerson	SNFS	2016-04-03
4-3	409	C196	37289909580309862111697012978469498997530066231388984708324720746304706221428537956177353.	P107		R Dickerson	SNFS	2016-04-05
11+8	289	C278	47710925766827777230325693915103491788429.	C237								S Batalov	SNFS	2016-04-06
5-4	397	C278	2647603938037522660530176148819684677321.	C239								S Batalov	SNFS	2016-04-06
6+5	383	C284	125828096035824850471308490303855554743239305664987.	P234							S Batalov	SNFS	2016-04-06

Thanks for the update, Paul. Here are some additions and corrections:

1) The sieving for 4-3,409 and 6+5,316 (shown above) was done by NFS@Home, with post-processing by Rich Dickerson. I don't know if you want the credit to reflect that.

2) You may want to have Serge verify his factoring method. The factors for 11+8,289, 5-4,397, and 6+5,383 (shown above) were almost certainly found by ECM.

3) 5-2,353 was factored by Greg Childers and NFS@Home, finishing on 2016-03-30. This date is before your April 1 cutoff, so I don't know how you want to handle that.

4) 6+5,317 was factored by Rich Dickerson and NFS@Home, reported on 2016-03-31. This one is already reflected in your tables, but doesn't appear in either the UPDATE.txt or HISTORICAL.txt files. Same issue with the April 1 cutoff.

[frmky]

One more that appears new.

Input number is 1053399044267294509146244166329554546187187488784697401831345601028946638716480355733506649101821883252517823647505939418001 (124 digits)
Using B1=11000000, B2=11000004, sigma=3:3074779521-3:3074780352 (832 curves)
GPU: Block: 16x32x1 Grid: 26x1x1 (832 parallel curves)
GPU: factor 2228832481126835646898014128351480452940801 found in Step 1 with curve 65 (-sigma 3:3074779586)
Computing 832 Step 1 took 58397ms of CPU time / 1645478ms of GPU time
********** Factor found in step 1: 2228832481126835646898014128351480452940801
Found prime factor of 43 digits: 2228832481126835646898014128351480452940801
Prime cofactor 472623695673496862039927365292760570243953018559793934205485776824630901144717201 has 81 digits

[unconnected]

4^487-3^487

Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=2151304656
Step 1 took 112149ms
Step 2 took 32752ms
********** Factor found in step 2: 47261792360897517780280887540726510506483
Found probable prime factor of 41 digits: 47261792360897517780280887540726510506483
Composite cofactor <...> has 225 digits

To coordinate our ECM efforts - I'm running curves with B1=11e6 on 4^n-3^n numbers.

[pinhodecarlos]

What about turning back on the ecmserver?

[frmky]

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!

Although directly running both stages worked, saving GPU stage 1 residues for later running with stage 2 doesn't. I posted a message on the ECM Discuss mailing list with a patch which should fix it.

[xilman]

Originally Posted by frmky

Although directly running both stages worked, saving GPU stage 1 residues for later running with stage 2 doesn't. I posted a message on the ECM Discuss mailing list with a patch which should fix it.

Ah. Guess what I just started running.

Oh well.


Paul

[frmky]

Originally Posted by xilman

Ah. Guess what I just started running.

Look in the save file to see if X=0x0. If so, it's broken.