Factoring humongous Cunningham numbers

[jyb]

Originally Posted by jyb

For the past 6 weeks, there's been a number on the reservation page reserved to someone going by the name "3^n+2^n". At first I figured well, why not? One name's as good as another. But it recently occurred to me that it's possible someone made a reservation accidentally, intending to enter that into e.g. the factorDB. It further occurred to me that it's even remotely possible that that someone could have been me.

Tom, is there anything that looks like a valid email address associated with that reservation?

Lacking any further information on this, and given that it had been sitting (apparently) idle for over six months, I decided to poach this one. My sincere apologies to anybody who might actually have been been working on this. I've sent the factor report to Paul and updated the factorDB.

[xilman]

First, the update to the present tables. The following 17 factorizations have been submitted in the last three months. There are now 92 composites left in the tables and it's time for an update.

11+10	227	C198	1047472063440383730117848473379013936859228242272837182003.	C141	J Becker		SNFS	2016-01-01
11+10	227	C141	802250825232013544325416946539837101176797832345614937893706713.	P78	J Becker		SNFS	2016-01-01
5+4	359	C187	14290394917843238690185067108955008815351388920412327.	P134	R Silverman		ECM	2016-01-05
5+4	344	C191	1964064606736264527732717504557743517420175392137553.	C139	R Silverman		ECM	2016-01-11
5+4	344	C139	106205153086904104536926820120269375042515743984509868962402041727329.	P71	J Becker		GNFS	2016-01-13
8-7	269	C234	63114004184218450772318216431038158607109067561.	C187	J Becker & NFS@Home	SNFS	2016-01-27
8-7	269	C187	4741515390811528985749791051638497031569341941056417119817991873989.	P120	J Becker & NFS@Home	SNFS	2016-01-27
11-6	227	C214	348577025191180887835967237696060299337187494921533447719346477876511820088031251.	P134	J Becker		GNFS	2016-02-01
7-3	277	C224	18743536303151641075879364530218456966384512914935576371711227009.	P160	J Becker		SNFS	2016-02-12
5+4	356	C241	3615007868608793847785602697238884068639280705513.	P192	R Silverman		ECM	2016-02-16
7+3	292	C197	8256607923444666350969659735860545455979767333334761509673.	P139	R Silverman		ECM	2016-02-18
11+2	227	C220	1611616644351756408713104298305976270685202497506570209627320290370839.	P151	J Becker		SNFS	2016-02-21
11-7	239	C197	165782579106668152224683824563992583035192962661670334562797.	P138	R Silverman		ECM	2016-02-24
8+3	262	C211	14198999110271335329012206374828969596434443711444902529.	C156	J Becker		SNFS	2016-03-03
8+3	262	C156	2973643393027006004509728522668697736031296935691741762585969.	P95	J Becker		SNFS	2016-03-03
5+2	353	C198	200546842057437737830821334966222809380510662622689.	C148	J Becker		GNFS	2016-03-15
5+2	353	C148	160496505085124984150551834270656167590489837755025476859.	P92	J Becker		GNFS	2016-03-15

Jon Becker and I have been putting in a lot of work for the extensions to the tables. Jon computed all the Aurifeuillian factorizations and has found many hundreds of factors. I've concentrated on loading the information into a robust PostgreSQL database, and getting it out again. We decided to set an upper limit of 1024 bits for the composites in the new tables; note that where Aur. factors are present, this limit applies to them too.

The report-generating code isn't yet finished but as soon as Jon sends in his final batch of factors I will release the new tables. Initially the reports will be hand-generated as at present and I'll try to keep errors to a minimum. The porting effort to the database has already turned up a few relatively trivial errors and rather more cases of inconsistent formatting.

As always, my thanks to everyone who has contributed to this effort over the years.

[ET_]

Originally Posted by xilman

We decided to set an upper limit of 1024 bits for the composites in the new tables; note that where Aur. factors are present, this limit applies to them too.

If you stay below 1019 bits, people could help you with GPU-ecm too...

[xilman]

Originally Posted by xilman

Jon Becker and I have been putting in a lot of work for the extensions to the tables. Jon computed all the Aurifeuillean factorizations and has found many hundreds of factors. I've concentrated on loading the information into a robust PostgreSQL database, and getting it out again. We decided to set an upper limit of 1024 bits for the composites in the new tables; note that where Aur. factors are present, this limit applies to them too.

The report-generating code isn't yet finished but as soon as Jon sends in his final batch of factors I will release the new tables. Initially the reports will be hand-generated as at present and I'll try to keep errors to a minimum.

Extended tables have now been posted to the web. Unfortunately the report generating code is still not finished so the format of all the files remains the same as before. Both Jon Becker and I have found many hundreds of relatively small factors already. My thanks also to Jon for sending me the rather complicated formulae for the Aurifeuillean factorizations. It is a pity that the displayed factorizations do not yet reflect the full structure of the HCN numbers themselves.

Over to you!

[xilman]

Originally Posted by ET_

If you stay below 1019 bits, people could help you with GPU-ecm too...

You should think more clearly about what you have just written. If it helps, the smallest composite in the newly extended tables has 106 digits.

[jyb]

Originally Posted by xilman

Extended tables have now been posted to the web. Unfortunately the report generating code is still not finished so the format of all the files remains the same as before. Both Jon Becker and I have found many hundreds of relatively small factors already. My thanks also to Jon for sending me the rather complicated formulae for the Aurifeuillean factorizations. It is a pity that the displayed factorizations do not yet reflect the full structure of the HCN numbers themselves.

Over to you!

Thanks for all the work in getting these out, Paul. Some statistics for those who are interested: digit-lengths of composites range from 106 to 307. SNFS difficulties range from 140 to 309. All of the new numbers have had a full t40 of ECM, plus 150 curves at B1 = 11e6, so there are quite a few composites which are ready for NFS (and some will be very quick jobs).

[Batalov]

Originally Posted by xilman

Extended tables have now been posted to the web. Unfortunately the report generating code is still not finished so the format of all the files remains the same as before. Both Jon Becker and I have found many hundreds of relatively small factors already. My thanks also to Jon for sending me the rather complicated formulae for the Aurifeuillean factorizations. It is a pity that the displayed factorizations do not yet reflect the full structure of the HCN numbers themselves.

Over to you!

Kudos! Nice extension!

Tom, would you consider loading the composites in your handy reservation system?

[Batalov]

Here, I prepared a key file for the composites in the gzipped list of all the composite cofactors

It is in the same order but only shows the first four digits of the composite (for control purposes, and to save space). One can

wget http://www.leyland.vispa.com/numth/factorization/anbn/comps.gz
gunzip comps.gz
paste comps_legend_short.txt comps > comps_legend_long.txt

if you want the complete file
The file starts like this:

7^301+2^301    c106    6679
11^267-5^267   c106    8600
5^363+3^363    c107    5828
8^325+7^325    c112    4640
12^257+5^257   c113    1202
... (1776 lines)

[Batalov]

Fri Apr  1 17:35:22 2016  
c140_8^300+7^300 = 
p68 factor: 66822113400011951652618283171640529391303131821475339773509674787201
p72 factor: 495371189436957658765155144706227119215564477711130641208983841925950401

c120_4^435-3^435 =
p49 factor: 1459017879468905078299839071484733623490504749961
p72 factor: 247293068918540595150176376396510281867889983255189378335600868477450341

Based on polcyclo(15); there are 24 more like these.

Similary, for polcyclo(21) there are 27.

P.S.
7^301+2^301 c106=
p40 factor: 2434210959900888334996422435526791766751
p67 factor: 2743877363481637358255305878433228888207795288530223054571783525407

[pinhodecarlos]

Input number is 2235978255761759817601345330954670662528812766190692497918026400842804230822872322093750951518481869291622260917177911 (118 digits)
Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=1:3046807465
Step 1 took 65037ms
Step 2 took 27113ms
********** Factor found in step 2: 5352206269748569346687694656502545328991
Found prime factor of 40 digits: 5352206269748569346687694656502545328991
Prime cofactor 417767579026209577107461771332578714014816921948156557862088912714375233070121 has 78 digits

[Batalov]

This one was already done by SNFS, but it is a good ECM hit anyway...