Smaller filtering run oddity

10metreh · 2009-01-04, 10:36

This occurred when I was trying to factor 2^293-309 with SNFS:

Code:

Sun Jan  4 10:04:30 2009  
Sun Jan  4 10:04:30 2009  
Sun Jan  4 10:04:30 2009  Msieve v. 1.39
Sun Jan  4 10:04:30 2009  random seeds: d5ad21b2 8ae26bdb
Sun Jan  4 10:04:30 2009  factoring 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057483 (89 digits)
Sun Jan  4 10:04:32 2009  no P-1/P+1/ECM available, skipping
Sun Jan  4 10:04:32 2009  commencing number field sieve (89-digit input)
Sun Jan  4 10:04:32 2009  R0: -9444732965739290427392
Sun Jan  4 10:04:32 2009  R1:  1
Sun Jan  4 10:04:32 2009  A0: -309
Sun Jan  4 10:04:32 2009  A1:  0
Sun Jan  4 10:04:32 2009  A2:  0
Sun Jan  4 10:04:32 2009  A3:  0
Sun Jan  4 10:04:32 2009  A4:  2
Sun Jan  4 10:04:32 2009  skew 1.00, size 3.580988e-09, alpha 1.471436, combined = 1.987871e-09
Sun Jan  4 10:04:32 2009  
Sun Jan  4 10:04:32 2009  commencing relation filtering
Sun Jan  4 10:04:33 2009  commencing duplicate removal, pass 1
Sun Jan  4 10:04:46 2009  found 1352 hash collisions in 864685 relations
Sun Jan  4 10:04:52 2009  added 141454 free relations
Sun Jan  4 10:04:52 2009  commencing duplicate removal, pass 2
Sun Jan  4 10:04:55 2009  found 0 duplicates and 1006139 unique relations
Sun Jan  4 10:04:55 2009  memory use: 36.1 MB
Sun Jan  4 10:04:55 2009  reading rational ideals above 327680
Sun Jan  4 10:04:55 2009  reading algebraic ideals above 327680
Sun Jan  4 10:04:55 2009  commencing singleton removal, pass 1
Sun Jan  4 10:05:52 2009  relations with 0 large ideals: 31936
Sun Jan  4 10:05:55 2009  relations with 1 large ideals: 264933
Sun Jan  4 10:05:55 2009  relations with 2 large ideals: 549612
Sun Jan  4 10:05:55 2009  relations with 3 large ideals: 21768
Sun Jan  4 10:05:55 2009  relations with 4 large ideals: 9
Sun Jan  4 10:05:55 2009  relations with 5 large ideals: 137881
Sun Jan  4 10:05:56 2009  relations with 6 large ideals: 0
Sun Jan  4 10:05:56 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:05:56 2009  1006139 relations and about 1372743 large ideals
Sun Jan  4 10:05:56 2009  commencing singleton removal, pass 2
Sun Jan  4 10:06:49 2009  found 599136 singletons
Sun Jan  4 10:07:01 2009  current dataset: 407003 relations and about 332990 large ideals
Sun Jan  4 10:07:06 2009  commencing singleton removal, pass 3
Sun Jan  4 10:08:11 2009  found 177321 singletons
Sun Jan  4 10:08:14 2009  current dataset: 229682 relations and about 134097 large ideals
Sun Jan  4 10:08:20 2009  commencing singleton removal, final pass
Sun Jan  4 10:08:49 2009  memory use: 9.8 MB
Sun Jan  4 10:08:49 2009  commencing in-memory singleton removal
Sun Jan  4 10:08:49 2009  begin with 229682 relations and 135225 unique ideals
Sun Jan  4 10:08:49 2009  reduce to 190726 relations and 95041 ideals in 8 passes
Sun Jan  4 10:08:49 2009  max relations containing the same ideal: 13
Sun Jan  4 10:08:50 2009  reading rational ideals above 163840
Sun Jan  4 10:08:50 2009  reading algebraic ideals above 163840
Sun Jan  4 10:08:50 2009  commencing singleton removal, final pass
Sun Jan  4 10:09:01 2009  keeping 481651 ideals with weight <= 20, new excess is 31667
Sun Jan  4 10:09:02 2009  memory use: 15.3 MB
Sun Jan  4 10:09:02 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:02 2009  begin with 263462 relations and 481651 unique ideals
Sun Jan  4 10:09:03 2009  reduce to 188886 relations and 117764 ideals in 8 passes
Sun Jan  4 10:09:03 2009  max relations containing the same ideal: 20
Sun Jan  4 10:09:03 2009  removing 59960 relations and 42766 ideals in 17194 cliques
Sun Jan  4 10:09:03 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:03 2009  begin with 128926 relations and 117764 unique ideals
Sun Jan  4 10:09:03 2009  reduce to 124735 relations and 70453 ideals in 5 passes
Sun Jan  4 10:09:03 2009  max relations containing the same ideal: 17
Sun Jan  4 10:09:03 2009  removing 40562 relations and 23368 ideals in 17194 cliques
Sun Jan  4 10:09:03 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:03 2009  begin with 84173 relations and 70453 unique ideals
Sun Jan  4 10:09:03 2009  reduce to 78666 relations and 40735 ideals in 6 passes
Sun Jan  4 10:09:03 2009  max relations containing the same ideal: 13
Sun Jan  4 10:09:03 2009  relations with 0 large ideals: 10285
Sun Jan  4 10:09:03 2009  relations with 1 large ideals: 29912
Sun Jan  4 10:09:03 2009  relations with 2 large ideals: 26323
Sun Jan  4 10:09:03 2009  relations with 3 large ideals: 9830
Sun Jan  4 10:09:03 2009  relations with 4 large ideals: 1724
Sun Jan  4 10:09:03 2009  relations with 5 large ideals: 589
Sun Jan  4 10:09:03 2009  relations with 6 large ideals: 3
Sun Jan  4 10:09:03 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:09:03 2009  commencing 2-way merge
Sun Jan  4 10:09:04 2009  reduce to 57483 relation sets and 19552 unique ideals
Sun Jan  4 10:09:04 2009  commencing full merge
Sun Jan  4 10:09:04 2009  memory use: 1.6 MB
Sun Jan  4 10:09:04 2009  found 37897 cycles, need 31867
Sun Jan  4 10:09:04 2009  weight of 31867 cycles is about 887091 (27.84/cycle)
Sun Jan  4 10:09:04 2009  distribution of cycle lengths:
Sun Jan  4 10:09:04 2009  1 relations: 10285
Sun Jan  4 10:09:04 2009  2 relations: 6462
Sun Jan  4 10:09:04 2009  3 relations: 4534
Sun Jan  4 10:09:04 2009  4 relations: 3538
Sun Jan  4 10:09:04 2009  5 relations: 2950
Sun Jan  4 10:09:04 2009  6 relations: 2158
Sun Jan  4 10:09:04 2009  7 relations: 1563
Sun Jan  4 10:09:04 2009  8 relations: 369
Sun Jan  4 10:09:04 2009  9 relations: 8
Sun Jan  4 10:09:04 2009  10+ relations: 0
Sun Jan  4 10:09:04 2009  heaviest cycle: 9 relations
Sun Jan  4 10:09:04 2009  matrix not dense enough, retrying
Sun Jan  4 10:09:05 2009  reading rational ideals above 131072
Sun Jan  4 10:09:05 2009  reading algebraic ideals above 131072
Sun Jan  4 10:09:05 2009  commencing singleton removal, final pass
Sun Jan  4 10:09:16 2009  keeping 487187 ideals with weight <= 25, new excess is 26131
Sun Jan  4 10:09:17 2009  memory use: 15.3 MB
Sun Jan  4 10:09:17 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:17 2009  begin with 263462 relations and 487187 unique ideals
Sun Jan  4 10:09:17 2009  reduce to 188876 relations and 123290 ideals in 8 passes
Sun Jan  4 10:09:17 2009  max relations containing the same ideal: 25
Sun Jan  4 10:09:17 2009  removing 60919 relations and 43282 ideals in 17637 cliques
Sun Jan  4 10:09:18 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:18 2009  begin with 127957 relations and 123290 unique ideals
Sun Jan  4 10:09:18 2009  reduce to 123437 relations and 75089 ideals in 5 passes
Sun Jan  4 10:09:18 2009  max relations containing the same ideal: 19
Sun Jan  4 10:09:18 2009  removing 41505 relations and 23868 ideals in 17637 cliques
Sun Jan  4 10:09:18 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:18 2009  begin with 81932 relations and 75089 unique ideals
Sun Jan  4 10:09:18 2009  reduce to 75964 relations and 44324 ideals in 6 passes
Sun Jan  4 10:09:18 2009  max relations containing the same ideal: 15
Sun Jan  4 10:09:18 2009  relations with 0 large ideals: 6815
Sun Jan  4 10:09:18 2009  relations with 1 large ideals: 22881
Sun Jan  4 10:09:18 2009  relations with 2 large ideals: 27008
Sun Jan  4 10:09:18 2009  relations with 3 large ideals: 14214
Sun Jan  4 10:09:18 2009  relations with 4 large ideals: 3773
Sun Jan  4 10:09:18 2009  relations with 5 large ideals: 1225
Sun Jan  4 10:09:18 2009  relations with 6 large ideals: 48
Sun Jan  4 10:09:18 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:09:18 2009  commencing 2-way merge
Sun Jan  4 10:09:18 2009  reduce to 54876 relation sets and 23236 unique ideals
Sun Jan  4 10:09:18 2009  commencing full merge
Sun Jan  4 10:09:19 2009  memory use: 1.8 MB
Sun Jan  4 10:09:19 2009  found 31039 cycles, need 26331
Sun Jan  4 10:09:19 2009  weight of 26331 cycles is about 1135175 (43.11/cycle)
Sun Jan  4 10:09:19 2009  distribution of cycle lengths:
Sun Jan  4 10:09:19 2009  1 relations: 6815
Sun Jan  4 10:09:19 2009  2 relations: 3743
Sun Jan  4 10:09:19 2009  3 relations: 2709
Sun Jan  4 10:09:19 2009  4 relations: 2263
Sun Jan  4 10:09:19 2009  5 relations: 2019
Sun Jan  4 10:09:19 2009  6 relations: 1727
Sun Jan  4 10:09:19 2009  7 relations: 1471
Sun Jan  4 10:09:19 2009  8 relations: 1317
Sun Jan  4 10:09:19 2009  9 relations: 1214
Sun Jan  4 10:09:19 2009  10+ relations: 3053
Sun Jan  4 10:09:19 2009  heaviest cycle: 15 relations
Sun Jan  4 10:09:19 2009  matrix can improve, retrying
Sun Jan  4 10:09:20 2009  reading rational ideals above 131072
Sun Jan  4 10:09:20 2009  reading algebraic ideals above 131072
Sun Jan  4 10:09:20 2009  commencing singleton removal, final pass
Sun Jan  4 10:09:31 2009  keeping 487190 ideals with weight <= 30, new excess is 26128
Sun Jan  4 10:09:32 2009  memory use: 15.3 MB
Sun Jan  4 10:09:32 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:32 2009  begin with 263462 relations and 487190 unique ideals
Sun Jan  4 10:09:32 2009  reduce to 188876 relations and 123293 ideals in 8 passes
Sun Jan  4 10:09:32 2009  max relations containing the same ideal: 29
Sun Jan  4 10:09:32 2009  removing 60919 relations and 43282 ideals in 17637 cliques
Sun Jan  4 10:09:32 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:33 2009  begin with 127957 relations and 123293 unique ideals
Sun Jan  4 10:09:33 2009  reduce to 123437 relations and 75092 ideals in 5 passes
Sun Jan  4 10:09:33 2009  max relations containing the same ideal: 19
Sun Jan  4 10:09:33 2009  removing 41505 relations and 23868 ideals in 17637 cliques
Sun Jan  4 10:09:33 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:33 2009  begin with 81932 relations and 75092 unique ideals
Sun Jan  4 10:09:33 2009  reduce to 75964 relations and 44327 ideals in 6 passes
Sun Jan  4 10:09:33 2009  max relations containing the same ideal: 15
Sun Jan  4 10:09:33 2009  relations with 0 large ideals: 6812
Sun Jan  4 10:09:33 2009  relations with 1 large ideals: 22875
Sun Jan  4 10:09:33 2009  relations with 2 large ideals: 27003
Sun Jan  4 10:09:33 2009  relations with 3 large ideals: 14225
Sun Jan  4 10:09:33 2009  relations with 4 large ideals: 3776
Sun Jan  4 10:09:33 2009  relations with 5 large ideals: 1224
Sun Jan  4 10:09:33 2009  relations with 6 large ideals: 49
Sun Jan  4 10:09:33 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:09:33 2009  commencing 2-way merge
Sun Jan  4 10:09:33 2009  reduce to 54876 relation sets and 23239 unique ideals
Sun Jan  4 10:09:33 2009  commencing full merge
Sun Jan  4 10:09:34 2009  memory use: 1.8 MB
Sun Jan  4 10:09:34 2009  found 31038 cycles, need 26328
Sun Jan  4 10:09:34 2009  weight of 26328 cycles is about 1135740 (43.14/cycle)
Sun Jan  4 10:09:34 2009  distribution of cycle lengths:
Sun Jan  4 10:09:34 2009  1 relations: 6812
Sun Jan  4 10:09:34 2009  2 relations: 3742
Sun Jan  4 10:09:34 2009  3 relations: 2707
Sun Jan  4 10:09:34 2009  4 relations: 2257
Sun Jan  4 10:09:34 2009  5 relations: 2018
Sun Jan  4 10:09:34 2009  6 relations: 1731
Sun Jan  4 10:09:34 2009  7 relations: 1471
Sun Jan  4 10:09:34 2009  8 relations: 1315
Sun Jan  4 10:09:34 2009  9 relations: 1219
Sun Jan  4 10:09:34 2009  10+ relations: 3056
Sun Jan  4 10:09:34 2009  heaviest cycle: 15 relations
Sun Jan  4 10:09:34 2009  matrix can improve, retrying
Sun Jan  4 10:09:34 2009  reading rational ideals above 131072
Sun Jan  4 10:09:34 2009  reading algebraic ideals above 131072
Sun Jan  4 10:09:34 2009  commencing singleton removal, final pass
Sun Jan  4 10:09:46 2009  keeping 487192 ideals with weight <= 35, new excess is 26126
Sun Jan  4 10:09:47 2009  memory use: 15.3 MB
Sun Jan  4 10:09:47 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:47 2009  begin with 263462 relations and 487192 unique ideals
Sun Jan  4 10:09:47 2009  reduce to 188876 relations and 123295 ideals in 8 passes
Sun Jan  4 10:09:47 2009  max relations containing the same ideal: 33
Sun Jan  4 10:09:47 2009  removing 60919 relations and 43282 ideals in 17637 cliques
Sun Jan  4 10:09:47 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:47 2009  begin with 127957 relations and 123295 unique ideals
Sun Jan  4 10:09:48 2009  reduce to 123437 relations and 75094 ideals in 5 passes
Sun Jan  4 10:09:48 2009  max relations containing the same ideal: 22
Sun Jan  4 10:09:48 2009  removing 41505 relations and 23868 ideals in 17637 cliques
Sun Jan  4 10:09:48 2009  commencing in-memory singleton removal
Sun Jan  4 10:09:48 2009  begin with 81932 relations and 75094 unique ideals
Sun Jan  4 10:09:48 2009  reduce to 75964 relations and 44329 ideals in 6 passes
Sun Jan  4 10:09:48 2009  max relations containing the same ideal: 15
Sun Jan  4 10:09:48 2009  relations with 0 large ideals: 6810
Sun Jan  4 10:09:48 2009  relations with 1 large ideals: 22866
Sun Jan  4 10:09:48 2009  relations with 2 large ideals: 27008
Sun Jan  4 10:09:48 2009  relations with 3 large ideals: 14230
Sun Jan  4 10:09:48 2009  relations with 4 large ideals: 3774
Sun Jan  4 10:09:48 2009  relations with 5 large ideals: 1226
Sun Jan  4 10:09:48 2009  relations with 6 large ideals: 50
Sun Jan  4 10:09:48 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:09:48 2009  commencing 2-way merge
Sun Jan  4 10:09:48 2009  reduce to 54876 relation sets and 23241 unique ideals
Sun Jan  4 10:09:48 2009  commencing full merge
Sun Jan  4 10:09:49 2009  memory use: 1.8 MB
Sun Jan  4 10:09:49 2009  found 31035 cycles, need 26326
Sun Jan  4 10:09:49 2009  weight of 26326 cycles is about 1135958 (43.15/cycle)
Sun Jan  4 10:09:49 2009  distribution of cycle lengths:
Sun Jan  4 10:09:49 2009  1 relations: 6810
Sun Jan  4 10:09:49 2009  2 relations: 3741
Sun Jan  4 10:09:49 2009  3 relations: 2705
Sun Jan  4 10:09:49 2009  4 relations: 2256
Sun Jan  4 10:09:49 2009  5 relations: 2021
Sun Jan  4 10:09:49 2009  6 relations: 1728
Sun Jan  4 10:09:49 2009  7 relations: 1471
Sun Jan  4 10:09:49 2009  8 relations: 1316
Sun Jan  4 10:09:49 2009  9 relations: 1219
Sun Jan  4 10:09:49 2009  10+ relations: 3059
Sun Jan  4 10:09:49 2009  heaviest cycle: 15 relations
Sun Jan  4 10:09:49 2009  matrix can improve, retrying
Sun Jan  4 10:09:49 2009  reading rational ideals above 131072
Sun Jan  4 10:09:49 2009  reading algebraic ideals above 131072
Sun Jan  4 10:09:49 2009  commencing singleton removal, final pass
Sun Jan  4 10:10:01 2009  keeping 487195 ideals with weight <= 40, new excess is 26123
Sun Jan  4 10:10:02 2009  memory use: 15.3 MB
Sun Jan  4 10:10:02 2009  commencing in-memory singleton removal
Sun Jan  4 10:10:02 2009  begin with 263462 relations and 487195 unique ideals
Sun Jan  4 10:10:02 2009  reduce to 188876 relations and 123298 ideals in 8 passes
Sun Jan  4 10:10:02 2009  max relations containing the same ideal: 40
Sun Jan  4 10:10:02 2009  removing 60921 relations and 43283 ideals in 17638 cliques
Sun Jan  4 10:10:02 2009  commencing in-memory singleton removal
Sun Jan  4 10:10:02 2009  begin with 127955 relations and 123298 unique ideals
Sun Jan  4 10:10:02 2009  reduce to 123433 relations and 75094 ideals in 5 passes
Sun Jan  4 10:10:02 2009  max relations containing the same ideal: 30
Sun Jan  4 10:10:02 2009  removing 41509 relations and 23871 ideals in 17638 cliques
Sun Jan  4 10:10:03 2009  commencing in-memory singleton removal
Sun Jan  4 10:10:03 2009  begin with 81924 relations and 75094 unique ideals
Sun Jan  4 10:10:03 2009  reduce to 75965 relations and 44334 ideals in 6 passes
Sun Jan  4 10:10:03 2009  max relations containing the same ideal: 20
Sun Jan  4 10:10:03 2009  relations with 0 large ideals: 6808
Sun Jan  4 10:10:03 2009  relations with 1 large ideals: 22842
Sun Jan  4 10:10:03 2009  relations with 2 large ideals: 27018
Sun Jan  4 10:10:03 2009  relations with 3 large ideals: 14236
Sun Jan  4 10:10:03 2009  relations with 4 large ideals: 3782
Sun Jan  4 10:10:03 2009  relations with 5 large ideals: 1228
Sun Jan  4 10:10:03 2009  relations with 6 large ideals: 51
Sun Jan  4 10:10:03 2009  relations with 7+ large ideals: 0
Sun Jan  4 10:10:03 2009  commencing 2-way merge
Sun Jan  4 10:10:03 2009  reduce to 54878 relation sets and 23247 unique ideals
Sun Jan  4 10:10:03 2009  commencing full merge
Sun Jan  4 10:10:04 2009  memory use: 1.8 MB
Sun Jan  4 10:10:04 2009  found 31034 cycles, need 26323
Sun Jan  4 10:10:04 2009  weight of 26323 cycles is about 1136431 (43.17/cycle)
Sun Jan  4 10:10:04 2009  distribution of cycle lengths:
Sun Jan  4 10:10:04 2009  1 relations: 6808
Sun Jan  4 10:10:04 2009  2 relations: 3737
Sun Jan  4 10:10:04 2009  3 relations: 2697
Sun Jan  4 10:10:04 2009  4 relations: 2258
Sun Jan  4 10:10:04 2009  5 relations: 2017
Sun Jan  4 10:10:04 2009  6 relations: 1728
Sun Jan  4 10:10:04 2009  7 relations: 1469
Sun Jan  4 10:10:04 2009  8 relations: 1322
Sun Jan  4 10:10:04 2009  9 relations: 1226
Sun Jan  4 10:10:04 2009  10+ relations: 3061
Sun Jan  4 10:10:04 2009  heaviest cycle: 15 relations
Sun Jan  4 10:10:04 2009  matrix not dense enough, retrying

At this point, msieve printed on screen:

Code:

error: too many merge attempts

This was with henryzz's second compilation in the "Msieve NFS minimum size" thread, the v1.39 without the new poly selection.

I tried again, but the same error appeared.

This factorization should be easy, so why did this happen?

MatWur-S530113 · 2009-01-04, 11:46

Hello,

maybe it is a problem if the number to factor has still 3 factors (I don't know for sure).
I got this factor with GMP-ECM:
2512367625515745823316347399

then I factored the remaining cofactor (61 digit) with msieve without any problem:

Code:

 
Sun Jan 04 12:39:56 2009 Msieve v. 1.38
Sun Jan 04 12:39:56 2009 random seeds: 573941e0 13092148
Sun Jan 04 12:39:56 2009 factoring 6334400827126655789146320853263788162714153399858827568268317 (61 digits)
Sun Jan 04 12:39:56 2009 searching for 15-digit factors
Sun Jan 04 12:39:57 2009 commencing quadratic sieve (61-digit input)
Sun Jan 04 12:39:57 2009 using multiplier of 17
Sun Jan 04 12:39:57 2009 using 32kb Intel Core sieve core
Sun Jan 04 12:39:57 2009 sieve interval: 6 blocks of size 32768
Sun Jan 04 12:39:57 2009 processing polynomials in batches of 34
Sun Jan 04 12:39:57 2009 using a sieve bound of 68713 (3400 primes)
Sun Jan 04 12:39:57 2009 using large prime bound of 3435650 (21 bits)
Sun Jan 04 12:39:57 2009 using trial factoring cutoff of 22 bits
Sun Jan 04 12:39:57 2009 polynomial 'A' values have 8 factors
Sun Jan 04 12:40:04 2009 3726 relations (1666 full + 2060 combined from 17012 partial), need 3496
Sun Jan 04 12:40:04 2009 begin with 18678 relations
Sun Jan 04 12:40:04 2009 reduce to 5488 relations in 2 passes
Sun Jan 04 12:40:04 2009 attempting to read 5488 relations
Sun Jan 04 12:40:04 2009 recovered 5488 relations
Sun Jan 04 12:40:04 2009 recovered 4720 polynomials
Sun Jan 04 12:40:04 2009 attempting to build 3726 cycles
Sun Jan 04 12:40:04 2009 found 3726 cycles in 1 passes
Sun Jan 04 12:40:04 2009 distribution of cycle lengths:
Sun Jan 04 12:40:04 2009 length 1 : 1666
Sun Jan 04 12:40:04 2009 length 2 : 2060
Sun Jan 04 12:40:04 2009 largest cycle: 2 relations
Sun Jan 04 12:40:04 2009 matrix is 3400 x 3726 (0.4 MB) with weight 101936 (27.36/col)
Sun Jan 04 12:40:04 2009 sparse part has weight 101936 (27.36/col)
Sun Jan 04 12:40:04 2009 filtering completed in 3 passes
Sun Jan 04 12:40:04 2009 matrix is 3161 x 3225 (0.4 MB) with weight 85336 (26.46/col)
Sun Jan 04 12:40:04 2009 sparse part has weight 85336 (26.46/col)
Sun Jan 04 12:40:04 2009 commencing Lanczos iteration
Sun Jan 04 12:40:04 2009 memory use: 0.5 MB
Sun Jan 04 12:40:04 2009 lanczos halted after 52 iterations (dim = 3158)
Sun Jan 04 12:40:04 2009 recovered 63 nontrivial dependencies
Sun Jan 04 12:40:05 2009 prp28 factor: 5180781695771039411729570263
Sun Jan 04 12:40:05 2009 prp34 factor: 1222672793238381544642569359055659
Sun Jan 04 12:40:05 2009 elapsed time 00:00:09

best regards,

Matthias

Batalov · 2009-01-04, 11:57

Code:

msieve -n 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057483
# => end of story in 30 minutes.
 
# better yet
echo 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057483 |ecm -c 200 25e4
...
Run 88 out of 200:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1173506587
Step 1 took 504ms
Step 2 took 356ms
********** Factor found in step 2: 5180781695771039411729570263
Found probable prime factor of 28 digits: 5180781695771039411729570263
Composite cofactor 3071803542331017086552710737407158208177897555176711820880941 has 61 digits
 
msieve -n 3071803542331017086552710737407158208177897555176711820880941 
...
Sun Jan  4 03:54:20 2009  lanczos halted after 49 iterations (dim = 3001)
Sun Jan  4 03:54:20 2009  recovered 64 nontrivial dependencies
Sun Jan  4 03:54:20 2009  prp28 factor: 2512367625515745823316347399
Sun Jan  4 03:54:20 2009  prp34 factor: 1222672793238381544642569359055659
Sun Jan  4 03:54:20 2009  elapsed time 00:00:10
Done in 5 minutes.

10metreh · 2009-01-04, 12:21

Quote:

Originally Posted by Batalov

Code:

msieve -n 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057483
# => end of story in 30 minutes.
 
# better yet
echo 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057483 |ecm -c 200 25e4
...
Run 88 out of 200:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1173506587
Step 1 took 504ms
Step 2 took 356ms
********** Factor found in step 2: 5180781695771039411729570263
Found probable prime factor of 28 digits: 5180781695771039411729570263
Composite cofactor 3071803542331017086552710737407158208177897555176711820880941 has 61 digits
 
msieve -n 3071803542331017086552710737407158208177897555176711820880941 
...
Sun Jan  4 03:54:20 2009  lanczos halted after 49 iterations (dim = 3001)
Sun Jan  4 03:54:20 2009  recovered 64 nontrivial dependencies
Sun Jan  4 03:54:20 2009  prp28 factor: 2512367625515745823316347399
Sun Jan  4 03:54:20 2009  prp34 factor: 1222672793238381544642569359055659
Sun Jan  4 03:54:20 2009  elapsed time 00:00:10
Done in 5 minutes.

So it's not a 2-brill after all. (Yep, that's why I was doing it...)

You do know your computer's far faster than mine, don't you?

Anyway, why did the filtering fail?

henryzz · 2009-01-04, 12:38

Quote:

Originally Posted by 10metreh

So it's not a 2-brill after all. (Yep, that's why I was doing it...)

You do know your computer's far faster than mine, don't you?

Anyway, why did the filtering fail?

try again with less relations
i have had that happen with too much oversieving

10metreh · 2009-01-04, 12:51

Quote:

Originally Posted by henryzz

try again with less relations
i have had that happen with too much oversieving

I don't need to try again now I know it isn't a 2-brilliant. I'm not trying to completely factor all the numbers near 2^293, I'm trying to find 2-brilliants in the area. This means that I eliminate a number once I know it is not a 2-brilliant.

henryzz · 2009-01-04, 12:52

Quote:

Originally Posted by 10metreh

I don't need to try again now I know it isn't a 2-brilliant.

true but it would be worthwhile learning why it failed in the first place

10metreh · 2009-01-04, 12:54

Quote:

Originally Posted by henryzz

true but it would be worthwhile learning why it failed in the first place

I'll remember to do it again once I find a 2-brilliant, but similar things might pop up along the way anyway.

jasonp · 2009-01-04, 14:37

Quote:

Originally Posted by 10metreh

I tried again, but the same error appeared.

This factorization should be easy, so why did this happen?

It was so easy you had twice as many relations as you needed. Paradoxically, NFS postprocessing is much more difficult under those circumstances. Greg is running into the same problem in another thread, this time with an enormous number.

10metreh · 2009-01-04, 15:12

Quote:

Originally Posted by jasonp

It was so easy you had twice as many relations as you needed. Paradoxically, NFS postprocessing is much more difficult under those circumstances. Greg is running into the same problem in another thread, this time with an enormous number.

I think I have tracked this one down to the def-par.txt file. The smallest SNFS parameters in def-par.txt are for 100 digits but my number had SNFS difficulty 89 digits. This meant the qintsize factLat.pl chose was far too high and it found many more relations than it needed. I think I'll have to add a 90 digits line with a lower qintsize.

11e (if it existed) or even 10e might be better for this size number!

10metreh · 2009-01-04, 18:44

Continuing my search, I reached 2^293-531. I had about 90% finished ECMing it to 20 digits when I had a thought: Maybe I'll get a factor off the very last curve? I hadn't had this happen before, but sure enough:

Code:

GMP-ECM 6.1.3 [powered by GMP 4.2.2] [ECM]
Input number is 2^293-531 (89 digits)
Run 77 out of 77:
Using B1=11000, B2=1873422, polynomial x^1, sigma=383869318
Step 1 took 188ms
Step 2 took 187ms
********** Factor found in step 2: 175238709850659009439
Found probable prime factor of 21 digits: 175238709850659009439
Probable prime cofactor (2^293-531)/175238709850659009439 has 68 digits

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Bug/oddity reports	fivemack	NFS@Home	1	2015-01-30 11:34
Attempts vs. Successes oddity	Rodrigo	GPU Computing	8	2014-09-19 08:44
Another server(?) oddity	Graff	PrimeNet	2	2010-01-25 17:00
Enormous filtering run oddity	frmky	Msieve	23	2009-11-03 18:52
Self-test oddity	JuanTutors	Software	1	2007-03-16 12:33