Factoring humongous Cunningham numbers - Page 59

xilman · 2008-09-26, 13:07

Quote:

Originally Posted by R.D. Silverman

I agree; these should be low priority. I am devoting only a single 8-year old machine to them (1.5GHz, 384M of DRAM)

And I even less. the machine around 10 years old (I forget precisely), a PII-400 also with 384M of RAM. It's primarily a print server and the token Windows box in an otherwise Unix-like environment.

Paul

bsquared · 2008-10-02, 17:29

Here is my petition to join the "100 digit cofactor club".

3^439 + 2^439 factors as:

Code:

Wed Oct 1 15:35:11 2008 Msieve v. 1.38
Wed Oct 1 15:35:11 2008 random seeds: 00d945fe aa2fb785
Wed Oct 1 15:35:11 2008 factoring 57182194393475387954810827224380735288919928867272127169467340082047563029566248187678442999408615699468589299198401102871170390688509792127442043240038186973436639332471330173723125996590602752739978375455631 (209 digits)
Wed Oct 1 15:35:13 2008 no P-1/P+1/ECM available, skipping
Wed Oct 1 15:35:13 2008 commencing number field sieve (209-digit input)
Wed Oct 1 15:35:13 2008 R0: 67585198634817523235520443624317923
Wed Oct 1 15:35:13 2008 R1: -9444732965739290427392
Wed Oct 1 15:35:13 2008 A0: 2
Wed Oct 1 15:35:13 2008 A1: 0
Wed Oct 1 15:35:13 2008 A2: 0
Wed Oct 1 15:35:13 2008 A3: 0
Wed Oct 1 15:35:13 2008 A4: 0
Wed Oct 1 15:35:13 2008 A5: 0
Wed Oct 1 15:35:13 2008 A6: 3
Wed Oct 1 15:35:13 2008 size score = 4.006280e-10, Murphy alpha = 1.523098, combined = 2.592680e-10
Wed Oct 1 15:35:13 2008 
Wed Oct 1 15:35:13 2008 commencing relation filtering
Wed Oct 1 15:35:13 2008 commencing duplicate removal, pass 1
Wed Oct 1 15:38:12 2008 error -6 reading relation 24855462
Wed Oct 1 15:39:15 2008 error -11 reading relation 34831650
Wed Oct 1 15:40:21 2008 error -11 reading relation 45177723
Wed Oct 1 15:41:09 2008 found 8449033 hash collisions in 52896721 relations
Wed Oct 1 15:41:24 2008 added 249 free relations
Wed Oct 1 15:41:24 2008 commencing duplicate removal, pass 2
Wed Oct 1 15:42:06 2008 found 5773904 duplicates and 47123066 unique relations
Wed Oct 1 15:42:06 2008 memory use: 270.4 MB
Wed Oct 1 15:42:06 2008 reading rational ideals above 30998528
Wed Oct 1 15:42:06 2008 reading algebraic ideals above 30998528
Wed Oct 1 15:42:06 2008 commencing singleton removal, pass 1
Wed Oct 1 15:47:23 2008 relations with 0 large ideals: 1189094
Wed Oct 1 15:47:24 2008 relations with 1 large ideals: 6071978
Wed Oct 1 15:47:24 2008 relations with 2 large ideals: 14593991
Wed Oct 1 15:47:24 2008 relations with 3 large ideals: 16576324
Wed Oct 1 15:47:24 2008 relations with 4 large ideals: 7631350
Wed Oct 1 15:47:24 2008 relations with 5 large ideals: 552
Wed Oct 1 15:47:24 2008 relations with 6 large ideals: 0
Wed Oct 1 15:47:24 2008 relations with 7+ large ideals: 1059777
Wed Oct 1 15:47:24 2008 47123066 relations and about 36241839 large ideals
Wed Oct 1 15:47:24 2008 commencing singleton removal, pass 2
Wed Oct 1 15:52:41 2008 found 10527467 singletons
Wed Oct 1 15:52:41 2008 current dataset: 36595599 relations and about 24577891 large ideals
Wed Oct 1 15:52:41 2008 commencing singleton removal, pass 3
Wed Oct 1 15:56:50 2008 found 2110200 singletons
Wed Oct 1 15:56:50 2008 current dataset: 34485399 relations and about 22408736 large ideals
Wed Oct 1 15:56:50 2008 commencing singleton removal, pass 4
Wed Oct 1 16:00:44 2008 found 424769 singletons
Wed Oct 1 16:00:44 2008 current dataset: 34060630 relations and about 21981295 large ideals
Wed Oct 1 16:00:44 2008 commencing singleton removal, final pass
Wed Oct 1 16:06:14 2008 memory use: 578.5 MB
Wed Oct 1 16:06:14 2008 commencing in-memory singleton removal
Wed Oct 1 16:06:18 2008 begin with 34060630 relations and 26897667 unique ideals
Wed Oct 1 16:07:04 2008 reduce to 27102783 relations and 19623163 ideals in 15 passes
Wed Oct 1 16:07:04 2008 max relations containing the same ideal: 36
Wed Oct 1 16:07:10 2008 reading rational ideals above 720000
Wed Oct 1 16:07:10 2008 reading algebraic ideals above 720000
Wed Oct 1 16:07:10 2008 commencing singleton removal, final pass
Wed Oct 1 16:14:10 2008 keeping 20805648 ideals with weight <= 20, new excess is 2650524
Wed Oct 1 16:14:43 2008 memory use: 694.3 MB
Wed Oct 1 16:14:43 2008 commencing in-memory singleton removal
Wed Oct 1 16:14:46 2008 begin with 27103034 relations and 20805648 unique ideals
Wed Oct 1 16:15:23 2008 reduce to 27099477 relations and 20800743 ideals in 11 passes
Wed Oct 1 16:15:23 2008 max relations containing the same ideal: 20
Wed Oct 1 16:15:41 2008 removing 2842628 relations and 2442628 ideals in 400000 cliques
Wed Oct 1 16:15:44 2008 commencing in-memory singleton removal
Wed Oct 1 16:15:47 2008 begin with 24256849 relations and 20800743 unique ideals
Wed Oct 1 16:16:10 2008 reduce to 24039695 relations and 18136568 ideals in 8 passes
Wed Oct 1 16:16:10 2008 max relations containing the same ideal: 20
Wed Oct 1 16:16:26 2008 removing 2095174 relations and 1695174 ideals in 400000 cliques
Wed Oct 1 16:16:28 2008 commencing in-memory singleton removal
Wed Oct 1 16:16:30 2008 begin with 21944521 relations and 18136568 unique ideals
Wed Oct 1 16:16:49 2008 reduce to 21818533 relations and 16313389 ideals in 7 passes
Wed Oct 1 16:16:49 2008 max relations containing the same ideal: 20
Wed Oct 1 16:17:03 2008 removing 1854764 relations and 1454764 ideals in 400000 cliques
Wed Oct 1 16:17:05 2008 commencing in-memory singleton removal
Wed Oct 1 16:17:07 2008 begin with 19963769 relations and 16313389 unique ideals
Wed Oct 1 16:17:24 2008 reduce to 19854502 relations and 14747546 ideals in 7 passes
Wed Oct 1 16:17:24 2008 max relations containing the same ideal: 20
Wed Oct 1 16:17:37 2008 removing 1730226 relations and 1330226 ideals in 400000 cliques
Wed Oct 1 16:17:38 2008 commencing in-memory singleton removal
Wed Oct 1 16:17:40 2008 begin with 18124276 relations and 14747546 unique ideals
Wed Oct 1 16:17:56 2008 reduce to 18019580 relations and 13310731 ideals in 7 passes
Wed Oct 1 16:17:56 2008 max relations containing the same ideal: 20
Wed Oct 1 16:18:07 2008 removing 1648586 relations and 1248586 ideals in 400000 cliques
Wed Oct 1 16:18:09 2008 commencing in-memory singleton removal
Wed Oct 1 16:18:11 2008 begin with 16370994 relations and 13310731 unique ideals
Wed Oct 1 16:18:22 2008 reduce to 16268164 relations and 11957379 ideals in 6 passes
Wed Oct 1 16:18:22 2008 max relations containing the same ideal: 20
Wed Oct 1 16:18:33 2008 removing 1590640 relations and 1190640 ideals in 400000 cliques
Wed Oct 1 16:18:34 2008 commencing in-memory singleton removal
Wed Oct 1 16:18:36 2008 begin with 14677524 relations and 11957379 unique ideals
Wed Oct 1 16:18:48 2008 reduce to 14567680 relations and 10654579 ideals in 7 passes
Wed Oct 1 16:18:48 2008 max relations containing the same ideal: 20
Wed Oct 1 16:18:57 2008 removing 1547894 relations and 1147894 ideals in 400000 cliques
Wed Oct 1 16:18:59 2008 commencing in-memory singleton removal
Wed Oct 1 16:19:00 2008 begin with 13019786 relations and 10654579 unique ideals
Wed Oct 1 16:19:11 2008 reduce to 12901584 relations and 9385751 ideals in 7 passes
Wed Oct 1 16:19:11 2008 max relations containing the same ideal: 19
Wed Oct 1 16:19:19 2008 removing 1523077 relations and 1123077 ideals in 400000 cliques
Wed Oct 1 16:19:20 2008 commencing in-memory singleton removal
Wed Oct 1 16:19:22 2008 begin with 11378507 relations and 9385751 unique ideals
Wed Oct 1 16:19:31 2008 reduce to 11249010 relations and 8129728 ideals in 7 passes
Wed Oct 1 16:19:31 2008 max relations containing the same ideal: 18
Wed Oct 1 16:19:38 2008 removing 257797 relations and 213123 ideals in 44674 cliques
Wed Oct 1 16:19:38 2008 commencing in-memory singleton removal
Wed Oct 1 16:19:39 2008 begin with 10991213 relations and 8129728 unique ideals
Wed Oct 1 16:19:46 2008 reduce to 10987798 relations and 7913179 ideals in 5 passes
Wed Oct 1 16:19:46 2008 max relations containing the same ideal: 18
Wed Oct 1 16:19:49 2008 relations with 0 large ideals: 473520
Wed Oct 1 16:19:49 2008 relations with 1 large ideals: 2038558
Wed Oct 1 16:19:49 2008 relations with 2 large ideals: 3672027
Wed Oct 1 16:19:49 2008 relations with 3 large ideals: 3139724
Wed Oct 1 16:19:49 2008 relations with 4 large ideals: 1329754
Wed Oct 1 16:19:49 2008 relations with 5 large ideals: 272841
Wed Oct 1 16:19:49 2008 relations with 6 large ideals: 28266
Wed Oct 1 16:19:49 2008 relations with 7+ large ideals: 33108
Wed Oct 1 16:19:49 2008 commencing 2-way merge
Wed Oct 1 16:19:58 2008 reduce to 7317493 relation sets and 4242874 unique ideals
Wed Oct 1 16:19:58 2008 commencing full merge
Wed Oct 1 16:20:55 2008 memory use: 377.5 MB
Wed Oct 1 16:20:56 2008 found 3682766 cycles, need 3267074
Wed Oct 1 16:20:59 2008 weight of 3267074 cycles is about 229114508 (70.13/cycle)
Wed Oct 1 16:20:59 2008 distribution of cycle lengths:
Wed Oct 1 16:20:59 2008 1 relations: 528665
Wed Oct 1 16:20:59 2008 2 relations: 346234
Wed Oct 1 16:20:59 2008 3 relations: 326745
Wed Oct 1 16:20:59 2008 4 relations: 307981
Wed Oct 1 16:20:59 2008 5 relations: 294961
Wed Oct 1 16:20:59 2008 6 relations: 271364
Wed Oct 1 16:20:59 2008 7 relations: 247800
Wed Oct 1 16:20:59 2008 8 relations: 220954
Wed Oct 1 16:20:59 2008 9 relations: 196157
Wed Oct 1 16:20:59 2008 10+ relations: 526213
Wed Oct 1 16:20:59 2008 heaviest cycle: 16 relations
Wed Oct 1 16:20:59 2008 commencing cycle optimization
Wed Oct 1 16:21:07 2008 start with 17768235 relations
Wed Oct 1 16:21:40 2008 pruned 706496 relations
Wed Oct 1 16:21:41 2008 memory use: 568.4 MB
Wed Oct 1 16:21:41 2008 distribution of cycle lengths:
Wed Oct 1 16:21:41 2008 1 relations: 528665
Wed Oct 1 16:21:41 2008 2 relations: 358311
Wed Oct 1 16:21:41 2008 3 relations: 344913
Wed Oct 1 16:21:41 2008 4 relations: 324136
Wed Oct 1 16:21:41 2008 5 relations: 311856
Wed Oct 1 16:21:41 2008 6 relations: 284811
Wed Oct 1 16:21:41 2008 7 relations: 259136
Wed Oct 1 16:21:41 2008 8 relations: 226083
Wed Oct 1 16:21:41 2008 9 relations: 195556
Wed Oct 1 16:21:41 2008 10+ relations: 433607
Wed Oct 1 16:21:41 2008 heaviest cycle: 16 relations
Wed Oct 1 16:21:47 2008 
Wed Oct 1 16:21:48 2008 commencing linear algebra
Wed Oct 1 16:21:49 2008 read 3267074 cycles
Wed Oct 1 16:22:08 2008 cycles contain 9454323 unique relations
Wed Oct 1 16:23:15 2008 read 9454323 relations
Wed Oct 1 16:23:33 2008 using 32 quadratic characters above 536869590
Wed Oct 1 16:24:47 2008 building initial matrix
Wed Oct 1 16:26:58 2008 memory use: 1164.2 MB
Wed Oct 1 16:27:00 2008 read 3267074 cycles
Wed Oct 1 16:27:22 2008 matrix is 3266474 x 3267074 (967.6 MB) with weight 301471637 (92.28/col)
Wed Oct 1 16:27:22 2008 sparse part has weight 217719647 (66.64/col)
Wed Oct 1 16:28:27 2008 filtering completed in 3 passes
Wed Oct 1 16:28:28 2008 matrix is 3256011 x 3256211 (965.6 MB) with weight 300764154 (92.37/col)
Wed Oct 1 16:28:28 2008 sparse part has weight 217300097 (66.73/col)
Wed Oct 1 16:29:42 2008 read 3256211 cycles
Wed Oct 1 16:30:02 2008 matrix is 3256011 x 3256211 (965.6 MB) with weight 300764154 (92.37/col)
Wed Oct 1 16:30:02 2008 sparse part has weight 217300097 (66.73/col)
Wed Oct 1 16:30:03 2008 saving the first 48 matrix rows for later
Wed Oct 1 16:30:04 2008 matrix is 3255963 x 3256211 (923.4 MB) with weight 230852110 (70.90/col)
Wed Oct 1 16:30:04 2008 sparse part has weight 209492109 (64.34/col)
Wed Oct 1 16:30:04 2008 matrix includes 64 packed rows
Wed Oct 1 16:30:04 2008 using block size 65536 for processor cache size 4096 kB
Wed Oct 1 16:30:49 2008 commencing Lanczos iteration (4 threads)
Wed Oct 1 16:30:49 2008 memory use: 969.7 MB
Thu Oct 2 10:59:58 2008 lanczos halted after 51489 iterations (dim = 3255963)
Thu Oct 2 11:00:04 2008 recovered 49 nontrivial dependencies
Thu Oct 2 11:00:05 2008 
Thu Oct 2 11:00:05 2008 commencing square root phase
Thu Oct 2 11:00:05 2008 reading relations for dependency 1
Thu Oct 2 11:00:06 2008 read 1628118 cycles
Thu Oct 2 11:00:14 2008 cycles contain 5793745 unique relations
Thu Oct 2 11:01:02 2008 read 5793745 relations
Thu Oct 2 11:01:38 2008 multiplying 4723334 relations
Thu Oct 2 11:11:20 2008 multiply complete, coefficients have about 120.09 million bits
Thu Oct 2 11:11:22 2008 initial square root is modulo 416483917
Thu Oct 2 11:28:02 2008 prp101 factor: 11002793910811144161014435718793615004311480896638730218231971013529964454715868109708331887058226403
Thu Oct 2 11:28:02 2008 prp109 factor: 5197061297066485000559393207060920940844164610691496239505184142209538391789630949485266788650611017865714277
Thu Oct 2 11:28:02 2008 elapsed time 19:52:51

xilman · 2008-10-05, 09:41

The tables have just been uploaded. There were 7 new complete factorizations in the last week, leaving 188 composites still to be done. Of the "old" tables, only 3+2, 3-2 and 5+4 need completing. The last of these has only one entry.
I'm already thinking about extending the tables but extensions won't be posted until the number of composites falls much lower.

Paul

xilman · 2008-11-28, 12:18

The tables have just been updated. There are 174 remaining composites now.

Thanks are due in this instance to Bob Silverman, Alex Greenbank, Ben Buhrow, Greg Childers, Tom Womack and Andreas Schindel for finding and then sending their factors to me.

My sincere apologies for taking very nearly 2 months to post an update. I can only plead ill-health, an excessive amount of work in Real Life(tm) and a machine which required a complete OS re-install before I could do anything useful.

Please keep the factors coming and I'll try to post updates a bit more frequently in future.

Paul

fatphil · 2008-11-28, 14:01

Quote:

Originally Posted by xilman

The tables have just been uploaded. There were 7 new complete factorizations in the last week, leaving 188 composites still to be done. Of the "old" tables, only 3+2, 3-2 and 5+4 need completing. The last of these has only one entry.
I'm already thinking about extending the tables but extensions won't be posted until the number of composites falls much lower.

I'm curious why, unlike other cyclotomic projects, you didn't take the vastly-easier aurefeuillian ones to twice the size? Unfortunately, I no longer have any record of the factorisations I performed a couple of years back (see my posts in the ~#300s in this thread) on any of my currently-alive machines, (or even of the scripts I was using), but I'm sure someone smart like Bob or yourself could recreate them.

fatphil · 2008-12-01, 17:25

Quote:

Originally Posted by fatphil

I'm curious why, unlike other cyclotomic projects, you didn't take the vastly-easier aurefeuillian ones to twice the size? Unfortunately, I no longer have any record of the factorisations I performed a couple of years back (see my posts in the ~#300s in this thread) on any of my currently-alive machines, (or even of the scripts I was using), but I'm sure someone smart like Bob or yourself could recreate them.

I'm not just curious, but actually perturbed that you've wasted time ECM-ing numbers which would have split trivially if you'd used Aurefeuillian factorisations. With the help of the wonderful clarity of thought of Dr Sardonicus, I've recreated my original formulae, and, in order to test them, I applied them to a few randomly selected numbers from your tables.

By luck I selected this row from 11+4:
187 6733.234499.7394729.7078756689004636971786089. C126

And I noticed the complete lack of 121260888412901704504061185001770658050780795481 as a factor.
I bet the cofactor splits very easily once that's taken out.

I suppose I ought to check 4+3, 5-4, 7+4,8+3,8+5, 8+7, 9+2, 9-5, 9+7, 9+8, 10+9, 11+4, etc. for other omissions.

bsquared · 2008-12-01, 17:55

Quote:

Originally Posted by fatphil

By luck I selected this row from 11+4:
187 6733.234499.7394729.7078756689004636971786089. C126

And I noticed the complete lack of 121260888412901704504061185001770658050780795481 as a factor.
I bet the cofactor splits very easily once that's taken out.

It splits trivially. The cofactor is (probably) prime:

Code:

5709159772448037211922834074597972300554167586081064642060063215601487922318323

Can you give an example of how Aurifeuillian factorizations work for homegeneous cunninghams or share your script?

R.D. Silverman · 2008-12-01, 18:05

Quote:

Originally Posted by bsquared

It splits trivially. The cofactor is (probably) prime:

Code:

5709159772448037211922834074597972300554167586081064642060063215601487922318323

Can you give an example of how Aurifeuillian factorizations work for homegeneous cunninghams or share your script?

example:

Code:

     6H    6H     2H    2H    
    3   + 2   = (3   + 2  )L.M      L = A - B   M = A + B   H = 2K - 1

         2H      H    2H             K  H    H
   A = 3   + 3.6  + 2        B = 6 (3  + 2 )

Riesel's book contains the coefficients for many of these.

R.D. Silverman · 2008-12-01, 18:19

Quote:

Originally Posted by fatphil

I suppose I ought to check 4+3, 5-4, 7+4,8+3,8+5, 8+7, 9+2, 9-5, 9+7, 9+8, 10+9, 11+4, etc. for other omissions.

Also
5^k + 2^k for k an odd multiple of 10
5^k + 3^k for k an odd multiple of 15
6^k + 5^k for k an odd multiple of 30,
7^k + 2^k for k an odd multiple of 14,
7,3- for odd multiples of 21 (minus side because 21 = 1 mod 4)
7,5+ for odd multiples of 35
7,6+ for odd multiples of 42
10,3+ for odd multiples of 30
10,7+ for odd multiples of 70
11,9+ for odd multiples of 11 (not 99 because 9 is already a square)
12,5+ for odd multiples of 15 (square free part of 60)
12,7- for odd multiples of 21 (square free part of 84)
12,11- for odd multiples of 33 (square free part of 132, 33=1 mod 4)

etc. etc. etc.

R.D. Silverman · 2008-12-01, 18:40

Quote:

Originally Posted by R.D. Silverman

Also
5^k + 2^k for k an odd multiple of 10
5^k + 3^k for k an odd multiple of 15
6^k + 5^k for k an odd multiple of 30,
7^k + 2^k for k an odd multiple of 14,
7,3- for odd multiples of 21 (minus side because 21 = 1 mod 4)
7,5+ for odd multiples of 35
7,6+ for odd multiples of 42
10,3+ for odd multiples of 30
10,7+ for odd multiples of 70
11,9+ for odd multiples of 11 (not 99 because 9 is already a square)
12,5+ for odd multiples of 15 (square free part of 60)
12,7- for odd multiples of 21 (square free part of 84)
12,11- for odd multiples of 33 (square free part of 132, 33=1 mod 4)

etc. etc. etc.

Note that 11,9,187+ listed as C130 has an Aurefeullian.

fatphil · 2008-12-01, 18:41

Quote:

Originally Posted by fatphil

I suppose I ought to check 4+3, 5-4, 7+4,8+3,8+5, 8+7, 9+2, 9-5, 9+7, 9+8, 10+9, 11+4, etc. for other omissions.

http://www.leyland.vispa.com/numth/f.../anbn/11+9.txt
187 1871.210784524898267.75233596333117435159. C130

C130 = 260777275385646300545894010485844710967932854733 * 8599161748379175860762190516255619473244408528122663325731373718516088821182884919

2008-10-05, 09:41	#641
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 3·3,529 Posts	Update The tables have just been uploaded. There were 7 new complete factorizations in the last week, leaving 188 composites still to be done. Of the "old" tables, only 3+2, 3-2 and 5+4 need completing. The last of these has only one entry. I'm already thinking about extending the tables but extensions won't be posted until the number of composites falls much lower. Paul

2008-11-28, 12:18	#642
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 3·3,529 Posts	Update The tables have just been updated. There are 174 remaining composites now. Thanks are due in this instance to Bob Silverman, Alex Greenbank, Ben Buhrow, Greg Childers, Tom Womack and Andreas Schindel for finding and then sending their factors to me. My sincere apologies for taking very nearly 2 months to post an update. I can only plead ill-health, an excessive amount of work in Real Life(tm) and a machine which required a complete OS re-install before I could do anything useful. Please keep the factors coming and I'll try to post updates a bit more frequently in future. Paul

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New phi for homogeneous Cunningham numbers	wpolly	Factoring	26	2016-07-29 04:34
Mathematics of Cunningham Numbers (3rd ed., 2002, A.M.S.)	Xyzzy	Cunningham Tables	42	2014-04-02 18:31
Don't know how to work on Cunningham numbers.	jasong	GMP-ECM	6	2006-06-30 08:51
Doing Cunningham numbers but messed up.	jasong	Factoring	1	2006-04-03 17:18
Need help factoring Cunningham numbers	jasong	Factoring	27	2006-03-21 02:47