mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)

 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
[/code]

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)
[/code]

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: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
[/code]

 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. :) )

 Mini-Geek 2008-02-27 12:15

[quote=fivemack;127119]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.[/quote]
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?

[b]Yes, that's correct[/b] -- fivemack

 fivemack 2008-03-05 15:28

Lucas(1233) =
[code]
19 *
45702379 *
Lucas(411) *
44287282091880235117923432515961253359268605892636945776483995749 *
159539728465877952283323572019287689118580024745329748535563445093460821051903111798130855082136071
[/code]

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=fivemack;127835]

<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.[/QUOTE]

Welcome to the club!!!!!:lol:

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=fivemack;127119]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.[/QUOTE]
I think this is a variant of formula (47) at [url]http://mathworld.wolfram.com/FibonacciNumber.html[/url] 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=fivemack;127119]There are enough post-primes-here threads around the forum; why not have a straight factor-reporting thread?

[/quote]

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 ([URL]http://www.oddperfect.org/[/URL]), 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
[SIZE=2]c5: 1[/SIZE]
[SIZE=2]c0: -421[/SIZE]
[SIZE=2]Y1: -1[/SIZE]
[SIZE=2]Y0: 31001674351559225686692396607441[/SIZE]

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

A couple of SNFS results

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
[/code]

All times are UTC. The time now is 04:26.