Gratuitous factors thread

fivemack · 2008-02-26, 22:03

There are enough post-primes-here threads around the forum; why not have a straight factor-reporting thread?

Fibonacci(1057) splits as

Code:

13 (from fib(7))
2113
5737 (from fib(151))
2811666624525811646469915877 (from fib(151))
138350496838007817946168356320856056973722649268262385229683944504459890710941261550861377381
579400004209795506836855348508059769276857157977636895767235484362787481855282292783501899717

The final factorisation of a C185 as a product of two P93s was a fairly easy SNFS job which happened to have a pretty result: I reckoned that Fibonacci numbers should have the same sorts of identities as Cunningham numbers do, and so used pari's linear-dependency code to find relations between fib(1057)/fib(151) and the terms a^6, a^5b, a^4b^2, a^3b^3, a^2b^4, ab^5, b^6 for a and b Fibonacci numbers.

It turns out that a nice polynomial is

Code:

X6  13
X5  -22
X4  20
X3  -15
X2  20
X1  -22
X0  13
Y0  9969216677189303386214405760200 = fibonacci(150)
Y1  -26099748102093884802012313146549 = fibonacci(152)

The polynomial is symmetrical, and indeed the various constructions for taking out factors of 13 and 21 giving sextics also work. Sadly, the problem that removing a factor five gives a degree-four polynomial is also there, and whilst you can get degree-six polynomials with smaller-than-random coefficients corresponding to a removed factor five, they're not enough smaller than random to be better than ignoring the factor five.

Sieving (small primes <20M both sides, 29-bit large primes, algebraic Q from 20M to 26M) with a version of ggnfs-lasieve14e with AMD64 inmost loops, provided by Joppe_Bos, took 350 CPU-hours on a quad-core between the evening of 20 Feb and the evening of 24 Feb; linear algebra took twelve hours elapsed on four cores with msieve-1.29 after 24 hours elapsed running msieve-1.33 failed twice.

Code:

Tue Feb 26 09:07:58 2008  Msieve v. 1.29
Tue Feb 26 09:07:58 2008  random seeds: 61c9c503 bb85da82
Tue Feb 26 09:07:58 2008  factoring 80160278450369029675301820882583949386439598567656024023074809662156062976897267540529441973163794688549751389930277383387860710672396567733782351879018091888240823999096047736754101177 (185 digits)
Tue Feb 26 09:07:58 2008  commencing number field sieve (185-digit input)
Tue Feb 26 09:07:59 2008  R0:  9969216677189303386214405760200
Tue Feb 26 09:07:59 2008  R1: -26099748102093884802012313146549
Tue Feb 26 09:07:59 2008  A0:  13
Tue Feb 26 09:07:59 2008  A1: -22
Tue Feb 26 09:07:59 2008  A2:  20
Tue Feb 26 09:07:59 2008  A3: -15
Tue Feb 26 09:07:59 2008  A4:  20
Tue Feb 26 09:07:59 2008  A5: -22
Tue Feb 26 09:07:59 2008  A6:  13
Tue Feb 26 09:07:59 2008  size score = 2.482582e-09, Murphy alpha = 0.457348, combined = 2.178482e-09
Tue Feb 26 09:08:33 2008  restarting with 46684329 relations
Tue Feb 26 09:08:33 2008  
Tue Feb 26 09:08:33 2008  commencing relation filtering
Tue Feb 26 09:08:33 2008  commencing duplicate removal, pass 1
Tue Feb 26 09:08:53 2008  error -10 reading relation 2538761
Tue Feb 26 09:09:30 2008  error -10 reading relation 7621819
Tue Feb 26 09:09:33 2008  error -5 reading relation 7939293
Tue Feb 26 09:15:08 2008  found 5218088 hash collisions in 46684326 relations
Tue Feb 26 09:15:08 2008  commencing duplicate removal, pass 2
Tue Feb 26 09:15:43 2008  found 1644119 duplicates and 45040207 unique relations
Tue Feb 26 09:15:43 2008  memory use: 153.2 MB
Tue Feb 26 09:15:58 2008  ignoring smallest 1765441 rational and 1764938 algebraic ideals
Tue Feb 26 09:15:58 2008  filtering ideals above 28411870
Tue Feb 26 09:15:58 2008  need 6001644 more relations than ideals
Tue Feb 26 09:15:58 2008  commencing singleton removal, pass 1
Tue Feb 26 09:21:52 2008  relations with 0 large ideals: 1246348
Tue Feb 26 09:21:52 2008  relations with 1 large ideals: 6481454
Tue Feb 26 09:21:52 2008  relations with 2 large ideals: 14712300
Tue Feb 26 09:21:52 2008  relations with 3 large ideals: 15765354
Tue Feb 26 09:21:52 2008  relations with 4 large ideals: 6834751
Tue Feb 26 09:21:52 2008  relations with 5 large ideals: 0
Tue Feb 26 09:21:52 2008  relations with 6 large ideals: 0
Tue Feb 26 09:21:52 2008  relations with 7+ large ideals: 0
Tue Feb 26 09:21:52 2008  45040207 relations and about 35198724 large ideals
Tue Feb 26 09:21:52 2008  commencing singleton removal, pass 2
Tue Feb 26 09:27:48 2008  found 11351344 singletons
Tue Feb 26 09:27:48 2008  current dataset: 33688863 relations and about 22558216 large ideals
Tue Feb 26 09:27:48 2008  commencing singleton removal, pass 3
Tue Feb 26 09:33:27 2008  found 2244020 singletons
Tue Feb 26 09:33:27 2008  current dataset: 31444843 relations and about 20250502 large ideals
Tue Feb 26 09:33:27 2008  commencing singleton removal, pass 4
Tue Feb 26 09:37:39 2008  found 445915 singletons
Tue Feb 26 09:37:39 2008  current dataset: 30998928 relations and about 19801800 large ideals
Tue Feb 26 09:37:39 2008  commencing singleton removal, final pass
Tue Feb 26 09:42:54 2008  memory use: 1069.9 MB
Tue Feb 26 09:42:54 2008  commencing in-memory singleton removal
Tue Feb 26 09:42:57 2008  begin with 30998928 relations and 24256194 unique ideals
Tue Feb 26 09:43:36 2008  reduce to 24129552 relations and 17058063 ideals in 14 passes
Tue Feb 26 09:43:36 2008  max relations containing the same ideal: 21
Tue Feb 26 09:43:50 2008  removing 2762897 relations and 2362897 ideals in 400000 cliques
Tue Feb 26 09:43:52 2008  commencing in-memory singleton removal
Tue Feb 26 09:43:54 2008  begin with 21366655 relations and 17058063 unique ideals
Tue Feb 26 09:44:19 2008  reduce to 21184591 relations and 14509433 ideals in 11 passes
Tue Feb 26 09:44:19 2008  max relations containing the same ideal: 21
Tue Feb 26 09:44:31 2008  removing 2039103 relations and 1639103 ideals in 400000 cliques
Tue Feb 26 09:44:32 2008  commencing in-memory singleton removal
Tue Feb 26 09:44:34 2008  begin with 19145488 relations and 14509433 unique ideals
Tue Feb 26 09:44:50 2008  reduce to 19025741 relations and 12748424 ideals in 8 passes
Tue Feb 26 09:44:50 2008  max relations containing the same ideal: 20
Tue Feb 26 09:45:01 2008  removing 1324891 relations and 1049219 ideals in 275672 cliques
Tue Feb 26 09:45:02 2008  commencing in-memory singleton removal
Tue Feb 26 09:45:04 2008  begin with 17700850 relations and 12748424 unique ideals
Tue Feb 26 09:45:15 2008  reduce to 17644945 relations and 11642541 ideals in 6 passes
Tue Feb 26 09:45:15 2008  max relations containing the same ideal: 18
Tue Feb 26 09:45:25 2008  removing 7328 relations and 6569 ideals in 759 cliques
Tue Feb 26 09:45:25 2008  commencing in-memory singleton removal
Tue Feb 26 09:45:27 2008  begin with 17637617 relations and 11642541 unique ideals
Tue Feb 26 09:45:29 2008  reduce to 17637617 relations and 11635972 ideals in 1 passes
Tue Feb 26 09:45:29 2008  max relations containing the same ideal: 18
Tue Feb 26 09:45:31 2008  dataset has 70.0% excess relations
Tue Feb 26 09:45:45 2008  ignoring smallest 1599304 rational and 1599464 algebraic ideals
Tue Feb 26 09:45:45 2008  filtering ideals above 25570683
Tue Feb 26 09:45:45 2008  need 5401480 more relations than ideals
Tue Feb 26 09:45:45 2008  commencing singleton removal, final pass
Tue Feb 26 09:48:35 2008  memory use: 545.0 MB
Tue Feb 26 09:48:35 2008  commencing in-memory singleton removal
Tue Feb 26 09:48:37 2008  begin with 17637617 relations and 11966014 unique ideals
Tue Feb 26 09:48:47 2008  reduce to 17622381 relations and 11950776 ideals in 6 passes
Tue Feb 26 09:48:47 2008  max relations containing the same ideal: 86
Tue Feb 26 09:48:56 2008  removing 674050 relations and 538988 ideals in 135062 cliques
Tue Feb 26 09:48:57 2008  commencing in-memory singleton removal
Tue Feb 26 09:48:59 2008  begin with 16948331 relations and 11950776 unique ideals
Tue Feb 26 09:49:07 2008  reduce to 16932010 relations and 11395346 ideals in 5 passes
Tue Feb 26 09:49:07 2008  max relations containing the same ideal: 82
Tue Feb 26 09:49:17 2008  removing 611009 relations and 475947 ideals in 135062 cliques
Tue Feb 26 09:49:17 2008  commencing in-memory singleton removal
Tue Feb 26 09:49:19 2008  begin with 16321001 relations and 11395346 unique ideals
Tue Feb 26 09:49:30 2008  reduce to 16307182 relations and 10905467 ideals in 6 passes
Tue Feb 26 09:49:30 2008  max relations containing the same ideal: 80
Tue Feb 26 09:49:39 2008  removing 2113 relations and 1879 ideals in 234 cliques
Tue Feb 26 09:49:39 2008  commencing in-memory singleton removal
Tue Feb 26 09:49:41 2008  begin with 16305069 relations and 10905467 unique ideals
Tue Feb 26 09:49:43 2008  reduce to 16305069 relations and 10903588 ideals in 1 passes
Tue Feb 26 09:49:43 2008  max relations containing the same ideal: 80
Tue Feb 26 09:49:49 2008  dataset has 53.0% excess relations
Tue Feb 26 09:50:01 2008  ignoring smallest 1432262 rational and 1431620 algebraic ideals
Tue Feb 26 09:50:01 2008  filtering ideals above 22729496
Tue Feb 26 09:50:03 2008  need 4321184 more relations than ideals
Tue Feb 26 09:50:03 2008  commencing singleton removal, final pass
Tue Feb 26 09:55:58 2008  memory use: 545.0 MB
Tue Feb 26 09:55:58 2008  commencing in-memory singleton removal
Tue Feb 26 09:56:00 2008  begin with 16305069 relations and 11237769 unique ideals
Tue Feb 26 09:56:10 2008  reduce to 16298227 relations and 11230927 ideals in 6 passes
Tue Feb 26 09:56:10 2008  max relations containing the same ideal: 84
Tue Feb 26 09:56:19 2008  removing 1473354 relations and 1100296 ideals in 373058 cliques
Tue Feb 26 09:56:20 2008  commencing in-memory singleton removal
Tue Feb 26 09:56:21 2008  begin with 14824873 relations and 11230927 unique ideals
Tue Feb 26 09:56:33 2008  reduce to 14739381 relations and 10043549 ideals in 7 passes
Tue Feb 26 09:56:33 2008  max relations containing the same ideal: 80
Tue Feb 26 09:56:42 2008  removing 1478198 relations and 1105140 ideals in 373058 cliques
Tue Feb 26 09:56:44 2008  commencing in-memory singleton removal
Tue Feb 26 09:56:45 2008  begin with 13261183 relations and 10043549 unique ideals
Tue Feb 26 09:56:55 2008  reduce to 13161373 relations and 8836505 ideals in 7 passes
Tue Feb 26 09:56:55 2008  max relations containing the same ideal: 73
Tue Feb 26 09:57:04 2008  removing 29069 relations and 25386 ideals in 3683 cliques
Tue Feb 26 09:57:04 2008  commencing in-memory singleton removal
Tue Feb 26 09:57:06 2008  begin with 13132304 relations and 8836505 unique ideals
Tue Feb 26 09:57:10 2008  reduce to 13132260 relations and 8811075 ideals in 3 passes
Tue Feb 26 09:57:10 2008  max relations containing the same ideal: 72
Tue Feb 26 09:57:12 2008  dataset has 22.4% excess relations
Tue Feb 26 09:57:28 2008  ignoring smallest 1263956 rational and 1262966 algebraic ideals
Tue Feb 26 09:57:28 2008  filtering ideals above 19888309
Tue Feb 26 09:57:28 2008  need 3812809 more relations than ideals
Tue Feb 26 09:57:28 2008  commencing singleton removal, final pass
Tue Feb 26 10:00:21 2008  memory use: 427.8 MB
Tue Feb 26 10:00:21 2008  commencing in-memory singleton removal
Tue Feb 26 10:00:23 2008  begin with 13132260 relations and 9147172 unique ideals
Tue Feb 26 10:00:32 2008  reduce to 13123839 relations and 9138751 ideals in 6 passes
Tue Feb 26 10:00:32 2008  max relations containing the same ideal: 76
Tue Feb 26 10:00:40 2008  removing 433127 relations and 346988 ideals in 86139 cliques
Tue Feb 26 10:00:41 2008  commencing in-memory singleton removal
Tue Feb 26 10:00:42 2008  begin with 12690712 relations and 9138751 unique ideals
Tue Feb 26 10:00:49 2008  reduce to 12682928 relations and 8783934 ideals in 5 passes
Tue Feb 26 10:00:49 2008  max relations containing the same ideal: 74
Tue Feb 26 10:00:57 2008  removing 378613 relations and 292474 ideals in 86139 cliques
Tue Feb 26 10:00:58 2008  commencing in-memory singleton removal
Tue Feb 26 10:00:59 2008  begin with 12304315 relations and 8783934 unique ideals
Tue Feb 26 10:01:06 2008  reduce to 12297618 relations and 8484730 ideals in 5 passes
Tue Feb 26 10:01:06 2008  max relations containing the same ideal: 73
Tue Feb 26 10:01:08 2008  dataset has 8.0% excess relations
Tue Feb 26 10:01:10 2008  relations with 0 large ideals: 91906
Tue Feb 26 10:01:10 2008  relations with 1 large ideals: 681265
Tue Feb 26 10:01:10 2008  relations with 2 large ideals: 2840946
Tue Feb 26 10:01:10 2008  relations with 3 large ideals: 4544444
Tue Feb 26 10:01:10 2008  relations with 4 large ideals: 3229255
Tue Feb 26 10:01:10 2008  relations with 5 large ideals: 905771
Tue Feb 26 10:01:10 2008  relations with 6 large ideals: 4024
Tue Feb 26 10:01:10 2008  relations with 7+ large ideals: 7
Tue Feb 26 10:01:10 2008  commencing 2-way merge
Tue Feb 26 10:01:22 2008  reduce to 8302574 relation sets and 4489686 unique ideals
Tue Feb 26 10:01:22 2008  commencing full merge
Tue Feb 26 10:03:53 2008  found 4147342 cycles, need 2919886
Tue Feb 26 10:03:56 2008  weight of 2919886 cycles is about 154335943 (52.86/cycle)
Tue Feb 26 10:03:56 2008  distribution of cycle lengths:
Tue Feb 26 10:03:56 2008  1 relations: 782600
Tue Feb 26 10:03:56 2008  2 relations: 385903
Tue Feb 26 10:03:56 2008  3 relations: 304758
Tue Feb 26 10:03:56 2008  4 relations: 269138
Tue Feb 26 10:03:56 2008  5 relations: 249355
Tue Feb 26 10:03:56 2008  6 relations: 232065
Tue Feb 26 10:03:56 2008  7 relations: 214749
Tue Feb 26 10:03:56 2008  8 relations: 192664
Tue Feb 26 10:03:56 2008  9 relations: 163643
Tue Feb 26 10:03:56 2008  10+ relations: 125011
Tue Feb 26 10:03:56 2008  heaviest cycle: 12 relations
Tue Feb 26 10:03:56 2008  matrix not dense enough, retrying
Tue Feb 26 10:03:57 2008  dataset has 8.0% excess relations
Tue Feb 26 10:04:08 2008  ignoring smallest 1094161 rational and 1092296 algebraic ideals
Tue Feb 26 10:04:08 2008  filtering ideals above 17047122
Tue Feb 26 10:04:08 2008  need 3812809 more relations than ideals
Tue Feb 26 10:04:08 2008  commencing singleton removal, final pass
Tue Feb 26 10:06:09 2008  memory use: 427.8 MB
Tue Feb 26 10:06:09 2008  commencing in-memory singleton removal
Tue Feb 26 10:06:11 2008  begin with 12297618 relations and 8824820 unique ideals
Tue Feb 26 10:06:19 2008  reduce to 12292838 relations and 8820040 ideals in 6 passes
Tue Feb 26 10:06:19 2008  max relations containing the same ideal: 73
Tue Feb 26 10:06:20 2008  dataset has -1.6% excess relations
Tue Feb 26 10:06:22 2008  relations with 0 large ideals: 91906
Tue Feb 26 10:06:22 2008  relations with 1 large ideals: 518702
Tue Feb 26 10:06:22 2008  relations with 2 large ideals: 2390850
Tue Feb 26 10:06:22 2008  relations with 3 large ideals: 4286603
Tue Feb 26 10:06:22 2008  relations with 4 large ideals: 3551153
Tue Feb 26 10:06:22 2008  relations with 5 large ideals: 1310709
Tue Feb 26 10:06:22 2008  relations with 6 large ideals: 136678
Tue Feb 26 10:06:22 2008  relations with 7+ large ideals: 6237
Tue Feb 26 10:06:22 2008  commencing 2-way merge
Tue Feb 26 10:06:33 2008  reduce to 8289324 relation sets and 4816526 unique ideals
Tue Feb 26 10:06:33 2008  commencing full merge
Tue Feb 26 10:09:16 2008  found 3915353 cycles, need 2712726
Tue Feb 26 10:09:18 2008  weight of 2712726 cycles is about 160120693 (59.03/cycle)
Tue Feb 26 10:09:18 2008  distribution of cycle lengths:
Tue Feb 26 10:09:18 2008  1 relations: 661530
Tue Feb 26 10:09:18 2008  2 relations: 306539
Tue Feb 26 10:09:18 2008  3 relations: 258942
Tue Feb 26 10:09:18 2008  4 relations: 238367
Tue Feb 26 10:09:18 2008  5 relations: 228364
Tue Feb 26 10:09:18 2008  6 relations: 217156
Tue Feb 26 10:09:18 2008  7 relations: 205383
Tue Feb 26 10:09:18 2008  8 relations: 190868
Tue Feb 26 10:09:18 2008  9 relations: 171372
Tue Feb 26 10:09:18 2008  10+ relations: 234205
Tue Feb 26 10:09:18 2008  heaviest cycle: 13 relations
Tue Feb 26 10:09:18 2008  matrix not dense enough, retrying
Tue Feb 26 10:09:19 2008  dataset has -1.6% excess relations
Tue Feb 26 10:09:28 2008  ignoring smallest 922548 rational and 921008 algebraic ideals
Tue Feb 26 10:09:28 2008  filtering ideals above 14205935
Tue Feb 26 10:09:28 2008  need 3812809 more relations than ideals
Tue Feb 26 10:09:28 2008  commencing singleton removal, final pass
Tue Feb 26 10:11:30 2008  memory use: 427.8 MB
Tue Feb 26 10:11:30 2008  commencing in-memory singleton removal
Tue Feb 26 10:11:31 2008  begin with 12297618 relations and 9167592 unique ideals
Tue Feb 26 10:11:40 2008  reduce to 12290840 relations and 9160814 ideals in 6 passes
Tue Feb 26 10:11:40 2008  max relations containing the same ideal: 73
Tue Feb 26 10:11:41 2008  dataset has -11.3% excess relations
Tue Feb 26 10:11:43 2008  relations with 0 large ideals: 91906
Tue Feb 26 10:11:43 2008  relations with 1 large ideals: 372899
Tue Feb 26 10:11:43 2008  relations with 2 large ideals: 1928669
Tue Feb 26 10:11:43 2008  relations with 3 large ideals: 3914092
Tue Feb 26 10:11:43 2008  relations with 4 large ideals: 3810493
Tue Feb 26 10:11:43 2008  relations with 5 large ideals: 1790949
Tue Feb 26 10:11:43 2008  relations with 6 large ideals: 347769
Tue Feb 26 10:11:43 2008  relations with 7+ large ideals: 34063
Tue Feb 26 10:11:43 2008  commencing 2-way merge
Tue Feb 26 10:11:55 2008  reduce to 8283314 relation sets and 5153288 unique ideals
Tue Feb 26 10:11:55 2008  commencing full merge
Tue Feb 26 10:14:56 2008  found 3750644 cycles, need 2561488
Tue Feb 26 10:14:59 2008  weight of 2561488 cycles is about 166852483 (65.14/cycle)
Tue Feb 26 10:14:59 2008  distribution of cycle lengths:
Tue Feb 26 10:14:59 2008  1 relations: 525516
Tue Feb 26 10:14:59 2008  2 relations: 255017
Tue Feb 26 10:14:59 2008  3 relations: 232994
Tue Feb 26 10:14:59 2008  4 relations: 223229
Tue Feb 26 10:14:59 2008  5 relations: 220595
Tue Feb 26 10:14:59 2008  6 relations: 212259
Tue Feb 26 10:14:59 2008  7 relations: 204608
Tue Feb 26 10:14:59 2008  8 relations: 193110
Tue Feb 26 10:14:59 2008  9 relations: 178116
Tue Feb 26 10:14:59 2008  10+ relations: 316044
Tue Feb 26 10:14:59 2008  heaviest cycle: 13 relations
Tue Feb 26 10:14:59 2008  commencing cycle optimization
Tue Feb 26 10:15:03 2008  start with 12944342 relations
Tue Feb 26 10:15:27 2008  pruned 318966 relations
Tue Feb 26 10:15:28 2008  distribution of cycle lengths:
Tue Feb 26 10:15:28 2008  1 relations: 525516
Tue Feb 26 10:15:28 2008  2 relations: 260946
Tue Feb 26 10:15:28 2008  3 relations: 241057
Tue Feb 26 10:15:28 2008  4 relations: 230100
Tue Feb 26 10:15:28 2008  5 relations: 230329
Tue Feb 26 10:15:28 2008  6 relations: 221452
Tue Feb 26 10:15:28 2008  7 relations: 213953
Tue Feb 26 10:15:28 2008  8 relations: 197789
Tue Feb 26 10:15:28 2008  9 relations: 177039
Tue Feb 26 10:15:28 2008  10+ relations: 263307
Tue Feb 26 10:15:28 2008  heaviest cycle: 13 relations
Tue Feb 26 10:15:29 2008  
Tue Feb 26 10:15:29 2008  commencing linear algebra
Tue Feb 26 10:15:33 2008  read 2561488 cycles
Tue Feb 26 10:15:42 2008  cycles contain 7467019 unique relations
Tue Feb 26 10:16:54 2008  read 7467019 relations
Tue Feb 26 10:17:08 2008  using 32 quadratic characters above 536865870
Tue Feb 26 10:21:19 2008  read 2561488 cycles
Tue Feb 26 10:22:15 2008  filtering completed in 3 passes
Tue Feb 26 10:22:16 2008  matrix is 2509266 x 2509465 with weight 221586585 (avg 88.30/col)
Tue Feb 26 10:22:39 2008  read 2509465 cycles
Tue Feb 26 10:22:41 2008  matrix is 2509266 x 2509465 with weight 221586585 (avg 88.30/col)
Tue Feb 26 10:22:42 2008  saving the first 48 matrix rows for later
Tue Feb 26 10:22:43 2008  matrix is 2509218 x 2509465 with weight 167640535 (avg 66.80/col)
Tue Feb 26 10:22:43 2008  matrix includes 64 packed rows
Tue Feb 26 10:22:43 2008  using block size 65536 for processor cache size 4096 kB
Tue Feb 26 10:23:07 2008  commencing Lanczos iteration (4 threads)
Tue Feb 26 21:01:14 2008  lanczos halted after 39684 iterations (dim = 2509213)
Tue Feb 26 21:01:19 2008  recovered 44 nontrivial dependencies
Tue Feb 26 21:01:20 2008  
Tue Feb 26 21:01:20 2008  commencing square root phase
Tue Feb 26 21:01:20 2008  reading relations for dependency 1
Tue Feb 26 21:01:20 2008  read 1254923 cycles
Tue Feb 26 21:01:24 2008  cycles contain 4429577 unique relations
Tue Feb 26 21:02:09 2008  read 4429577 relations
Tue Feb 26 21:02:41 2008  multiplying 6203778 relations
Tue Feb 26 21:19:22 2008  multiply complete, coefficients have about 170.77 million bits
Tue Feb 26 21:19:29 2008  initial square root is modulo 1344767
Tue Feb 26 21:39:50 2008  prp93 factor: 138350496838007817946168356320856056973722649268262385229683944504459890710941261550861377381
Tue Feb 26 21:39:50 2008  prp93 factor: 579400004209795506836855348508059769276857157977636895767235484362787481855282292783501899717
Tue Feb 26 21:39:50 2008  elapsed time 12:31:52

jasong · 2008-02-27, 05:22

I've never tried any of these programs, except ecm. When you talk about failures, is it stuff that you have to tweak, or does the program have some sort of method for cycling through various combinations? I have no idea what kind of combinations, but it seems like there are different variations that can be tried, or maybe I'm just reading non math intensive comments in the factoring threads wrong.

(It's fun to scan the math threads for stuff that makes sense. Not that the rest is nonsensical, but if you don't have the knowledge it's mostly gobble-de-gook. :) )

TimSorbet · 2008-02-27, 12:15

Quote:

Originally Posted by fivemack

The final factorisation of a C185 as a product of two P93s was a fairly easy SNFS job which happened to have a pretty result: I reckoned that Fibonacci numbers should have the same sorts of identities as Cunningham numbers do, and so used pari's linear-dependency code to find relations between fib(1057)/fib(151) and the terms a^6, a^5b, a^4b^2, a^3b^3, a^2b^4, ab^5, b^6 for a and b Fibonacci numbers.

Sorry to post off-topic, but what is meant by something like "C185" or "P93"?
Just as I'm asking this question I thought of what it might be, just based on the letters...C185 means a composite, 185-digit number, and P93 means a prime, 93 digit number. Is that shot in the dark at all right? Or something to do with Cunningham numbers?

Yes, that's correct -- fivemack

fivemack · 2008-03-05, 15:28

Lucas(1233) =

Code:

19 *
45702379 *
Lucas(411) * 
44287282091880235117923432515961253359268605892636945776483995749 *
159539728465877952283323572019287689118580024745329748535563445093460821051903111798130855082136071

SNFS difficulty 171.8, took about a week on a few computers, would have been quicker if the reaction to running out of disc quota on the server wasn't to lose writes silently so one file had 200MB of zeroes in the middle where relations should have been.

R.D. Silverman · 2008-03-05, 16:06

Quote:

Originally Posted by fivemack

<snip>

reaction to running out of disc quota on the server wasn't to lose writes silently so one file had 200MB of zeroes in the middle where relations should have been.

Welcome to the club!!!!!

I've had entire collections of sievers shut down because some retard
decided to dump multi-gigabytes of data onto a shared file system and
thereby run it out of space. It leaves corrupted records at the ends
of my output files. This has happened at least a half-dozen times.
Naturally the users who do this never bother to check if there is enough
space before they dump their data......

maxal · 2008-03-07, 02:46

Quote:

Originally Posted by fivemack

I reckoned that Fibonacci numbers should have the same sorts of identities as Cunningham numbers do, and so used pari's linear-dependency code to find relations between fib(1057)/fib(151) and the terms a^6, a^5b, a^4b^2, a^3b^3, a^2b^4, ab^5, b^6 for a and b Fibonacci numbers.

I think this is a variant of formula (47) at http://mathworld.wolfram.com/FibonacciNumber.html for k=7 and n=151.
This formula can be used directly to get a polynomial representation of degree k-1:

$F_{kn}/F_n = \sum_{j=1}^k {k\choose j} F_j x^{j-1} y^{k-j}$

where $x=F_n$ and $y=F_{n-1}$ .

bsquared · 2008-03-09, 16:34

Quote:

Originally Posted by fivemack

There are enough post-primes-here threads around the forum; why not have a straight factor-reporting thread?

I like this idea. I respect what the prime finding people are doing, but for whatever reason I like factoring instead. So I'll post the biggest factorizations I've done by various methods, and post updates as I break my own records. I think that is the spirit of this thread, no?

Most of these efforts come from the odd perfect number search (http://www.oddperfect.org/), which I've been involved with for a year or so now.

To start:

421^59-1 (C144, difficulty 157.46) by SNFS factors as
8769524964618840768473228417817739675245059818515901 *
35824627104830457305942978653803062873922140670229459114188957954764951096171385903989548363

using the polynomial
c5: 1
c0: -421
Y1: -1
Y0: 31001674351559225686692396607441

6M relations from ggnfs 13e siever on one core of a Athlon64 2.2GHz for a few days followed by msieve postprocessing to produce a 395010 x 395258 matrix with weight 25331768

- ben.

bsquared · 2008-03-09, 16:43

By GNFS, the 125 digit cofactor of 1119387697^19-1 factors as

3484602912243398707185898705317541418197499305758241 *
8829353630392603956189074833285818490567582542294628525126057810179844037

~10M relations over a week or so of sieving on one core of a 2.2GHz Athlon64, followed by msieve postprocessing to produce and solve a 826086 x 826334 matrix with weight 60653808.

bsquared · 2008-03-09, 16:52

By P-1, the C135 cofactor of 64271^37-1 factors as
274817637397314759415229527351079 * P102

using a version of P-1 which I wrote, with a stage one bound of 1e8 and stage two bound of 2e9.

bsquared · 2008-03-09, 16:59

By QS, 11^174+10^174 (C103) factors as

8055091904195531129734494480052194800703416701 *
282676276623675825398802382490193608881327644834991216513

after about 5 hours sieving using msieve 1.33 on 4 Xeon 5160 cores

joral · 2008-03-17, 23:08

I've just completed a few factorizations from the homogeneous cunningham reservation list.

Code:

11,6,136+ (C134) 917147464621732445846263197551265176491969916515669969.P80
11,8,136+ (C116) 3019860452197352866441914806309105477611721850147079815601.P59
11,9,136+ (C119) 20392009066511518061382980231029180353909229649.P73

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gratuitous OPN factors	wblipp	Factoring	463	2019-05-30 07:19
Ungracious Factors Thread	FactorEyes	Factoring	2	2011-04-09 05:45
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
JasonG's gratuitous C++ thread	jasong	Programming	16	2006-11-07 01:03
Gratuitous hardware-related banana thread	GP2	Hardware	7	2003-11-24 06:13

2008-02-27, 05:22	#2
jasong "Jason Goatcher" Mar 2005 3×7×167 Posts	I've never tried any of these programs, except ecm. When you talk about failures, is it stuff that you have to tweak, or does the program have some sort of method for cycling through various combinations? I have no idea what kind of combinations, but it seems like there are different variations that can be tried, or maybe I'm just reading non math intensive comments in the factoring threads wrong. (It's fun to scan the math threads for stuff that makes sense. Not that the rest is nonsensical, but if you don't have the knowledge it's mostly gobble-de-gook. :) )

2008-03-05, 15:28	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	Lucas(1233) = Code: 19 * 45702379 * Lucas(411) * 44287282091880235117923432515961253359268605892636945776483995749 * 159539728465877952283323572019287689118580024745329748535563445093460821051903111798130855082136071 SNFS difficulty 171.8, took about a week on a few computers, would have been quicker if the reaction to running out of disc quota on the server wasn't to lose writes silently so one file had 200MB of zeroes in the middle where relations should have been.

2008-03-09, 16:43	#8
bsquared "Ben" Feb 2007 3,733 Posts	By GNFS, the 125 digit cofactor of 1119387697^19-1 factors as 3484602912243398707185898705317541418197499305758241 * 8829353630392603956189074833285818490567582542294628525126057810179844037 ~10M relations over a week or so of sieving on one core of a 2.2GHz Athlon64, followed by msieve postprocessing to produce and solve a 826086 x 826334 matrix with weight 60653808.

2008-03-09, 16:52	#9
bsquared "Ben" Feb 2007 3,733 Posts	By P-1, the C135 cofactor of 64271^37-1 factors as 274817637397314759415229527351079 * P102 using a version of P-1 which I wrote, with a stage one bound of 1e8 and stage two bound of 2e9.

2008-03-09, 16:59	#10
bsquared "Ben" Feb 2007 3733₁₀ Posts	By QS, 11^174+10^174 (C103) factors as 8055091904195531129734494480052194800703416701 * 282676276623675825398802382490193608881327644834991216513 after about 5 hours sieving using msieve 1.33 on 4 Xeon 5160 cores