Running Msieve

[jasonp]

Originally Posted by Timmy

I tried factoring the GGNFS RSA110 test with msieve and it failed in the lanczos stage. The error occurs in lanczos_matmul.c @ line 354 and its an access violation.

Could you PM or email me the log from the factorization, the OS and compiler, and the commands that you used?

[fivemack]

Is there any way that the square-root phase could be made to run N trials in parallel in different threads? At the moment, for a 117-digit number where I've been moderately unlucky, the four square root attempts required to get the factors actually take slightly longer than the linear algebra.

Or is running two FFT-multiplies in parallel just going to exhaust the memory bandwidth and run no faster than running them in series?

Sun Aug 19 22:57:13 2007  commencing Lanczos iteration (2 threads)
Sun Aug 19 23:32:26 2007  lanczos halted after 8097 iterations
... fourth dependency
Mon Aug 20 00:06:54 2007  initial square root is modulo 117610387
Mon Aug 20 00:13:20 2007  prp55 factor: 8407983879296823740247134700801995624216958869872798789

[dleclair]

I haven't tried two instances on one machine so I can't vouch for the performance impact but you can try it yourself using the -nc3 X,Y switch to run the square root stage for only dependencies X through Y. I'm doing that right now for a C123 but with instances running on two different machines.

-Don Leclair

[jasonp]

Originally Posted by dleclair

I haven't tried two instances on one machine so I can't vouch for the performance impact but you can try it yourself using the -nc3 X,Y switch to run the square root stage for only dependencies X through Y. I'm doing that right now for a C123 but with instances running on two different machines.

-Don Leclair

This is how I intended the square root to be run in parallel. It's no trouble at all to run different dependencies in different threads, but I didn't want to risk this because it would multiply the memory use of the square root by approximately the number of threads (right now each dependency only needs the relations that contribute to that dependency, and the main constraining factor in the square root is the size of the intermediate number field elements that are generated).

The best way to multithread the square root is to multithread the underlying FFT multiply; there is enough computation there that it's reasonable to expect a nontrivial speedup for a single dependency. Of course, you can also use a multithread-capable library like FFTW and make the underlying transforms 5-10x faster before threading, but the memory use will increase and you will contract the GPL virus to boot.

Originally Posted by jasonp

Now available. This is primarily to propagate a fix for a fairly major NFS filtering bug. There's also a bug in the linear algebra for people using MSVC (reported by Timmy above), and I'm working on a fix.

Happy factoring,
jasonp

Hi,

I have trouble compiling Version 1.26/1.25/1.23 on Mac OS X (Intel). Version 1.17 compiled without problems. I tried several different -march flags, but I always get the following error. Any can anyone help me?


gcc -O3 -fomit-frame-pointer -DNDEBUG -march=k8 -Wall -W -Wconversion -Iinclude demo.c -o msieve -lm libmsieve.a
/usr/bin/ld: Undefined symbols:
_qs_core_sieve_core_32k
_qs_core_sieve_k7_64k
_qs_core_sieve_k7xp_64k
_qs_core_sieve_k8_64k
_qs_core_sieve_p2_64k
_qs_core_sieve_p3_64k
_qs_core_sieve_p4_64k
_qs_core_sieve_pm_32k
collect2: ld returned 1 exit status
make: *** [generic] Error 1

[frmky]

Hi,

I got odd output from a recent factorization. Here's the log file:

Fri Aug 24 10:59:04 2007  
Fri Aug 24 10:59:04 2007  
Fri Aug 24 10:59:04 2007  Msieve v. 1.26
Fri Aug 24 10:59:04 2007  random seeds: 5352e230 f7437ae4
Fri Aug 24 10:59:04 2007  factoring 4983000749357254885411154805085655665807897923208793203850967520402559118199929302012595434742057349183255915200977706102576390499846482335519021 (145 digits)
Fri Aug 24 10:59:04 2007  commencing number field sieve (145-digit input)
Fri Aug 24 10:59:04 2007  R0: -664613997892457936451903530140172288
Fri Aug 24 10:59:04 2007  R1:  12157665459056928801
Fri Aug 24 10:59:04 2007  A0:  1
Fri Aug 24 10:59:04 2007  A1:  0
Fri Aug 24 10:59:04 2007  A2:  0
Fri Aug 24 10:59:04 2007  A3:  0
Fri Aug 24 10:59:04 2007  A4:  0
Fri Aug 24 10:59:04 2007  A5:  12
Fri Aug 24 10:59:04 2007  size score = 0.000000e+000, Murphy alpha = 0.000000, combined = 0.000000e+000
Fri Aug 24 11:00:25 2007  restarting with 26517941 relations
Fri Aug 24 11:00:26 2007  generating factor base
Fri Aug 24 11:00:34 2007  factor base complete:
Fri Aug 24 11:00:34 2007  695609 rational roots (max prime = 10499981)
Fri Aug 24 11:00:34 2007  696004 algebraic roots (max prime = 10499963)
Fri Aug 24 11:00:36 2007  added 34852 free relations
Fri Aug 24 11:00:36 2007  
Fri Aug 24 11:00:36 2007  commencing relation filtering
Fri Aug 24 11:00:36 2007  commencing duplicate removal, pass 1
Fri Aug 24 11:01:12 2007  error -14 reading relation 2741751
Fri Aug 24 11:01:13 2007  error -8 reading relation 2832550
Fri Aug 24 11:03:25 2007  error -14 reading relation 14269337
Fri Aug 24 11:03:25 2007  error -10 reading relation 14274055
Fri Aug 24 11:03:28 2007  error -4 reading relation 14453729
Fri Aug 24 11:03:46 2007  error -14 reading relation 16055560
Fri Aug 24 11:03:48 2007  error -14 reading relation 16204391
Fri Aug 24 11:03:48 2007  error -14 reading relation 16205278
Fri Aug 24 11:03:48 2007  error -8 reading relation 16217456
Fri Aug 24 11:03:50 2007  error -8 reading relation 16357117
Fri Aug 24 11:03:51 2007  error -4 reading relation 16510937
Fri Aug 24 11:04:04 2007  error -14 reading relation 17581823
Fri Aug 24 11:04:04 2007  error -14 reading relation 17611501
Fri Aug 24 11:04:06 2007  error -14 reading relation 17779084
Fri Aug 24 11:04:08 2007  error -8 reading relation 17942848
Fri Aug 24 11:04:08 2007  error -8 reading relation 17943179
Fri Aug 24 11:04:08 2007  error -10 reading relation 17943436
Fri Aug 24 11:05:49 2007  found 2763734 hash collisions in 26552776 relations
Fri Aug 24 11:05:49 2007  commencing duplicate removal, pass 2
Fri Aug 24 11:07:57 2007  found 1643946 duplicates and 24908830 unique relations
Fri Aug 24 11:07:57 2007  memory use: 94.6 MB
Fri Aug 24 11:08:03 2007  ignoring smallest 642308 rational and 642499 algebraic ideals
Fri Aug 24 11:08:03 2007  filtering rational ideals above 9639820
Fri Aug 24 11:08:03 2007  filtering algebraic ideals above 9639820
Fri Aug 24 11:08:03 2007  need 2184171 more relations than ideals
Fri Aug 24 11:08:03 2007  commencing singleton removal, pass 1
Fri Aug 24 11:13:12 2007  relations with 0 large ideals: 505835
Fri Aug 24 11:13:12 2007  relations with 1 large ideals: 3474725
Fri Aug 24 11:13:12 2007  relations with 2 large ideals: 8744253
Fri Aug 24 11:13:12 2007  relations with 3 large ideals: 8893492
Fri Aug 24 11:13:12 2007  relations with 4 large ideals: 3135769
Fri Aug 24 11:13:12 2007  relations with 5 large ideals: 149567
Fri Aug 24 11:13:12 2007  relations with 6 large ideals: 5174
Fri Aug 24 11:13:12 2007  relations with 7+ large ideals: 15
Fri Aug 24 11:13:12 2007  24908830 relations and about 17374947 large ideals
Fri Aug 24 11:13:12 2007  commencing singleton removal, pass 2
Fri Aug 24 11:18:24 2007  found 6594105 singletons
Fri Aug 24 11:18:24 2007  current dataset: 18314725 relations and about 10262866 large ideals
Fri Aug 24 11:18:24 2007  commencing singleton removal, pass 3
Fri Aug 24 11:22:28 2007  found 669849 singletons
Fri Aug 24 11:22:28 2007  current dataset: 17644876 relations and about 9584985 large ideals
Fri Aug 24 11:22:29 2007  commencing singleton removal, pass 4
Fri Aug 24 11:26:26 2007  found 67170 singletons
Fri Aug 24 11:26:26 2007  current dataset: 17577706 relations and about 9517711 large ideals
Fri Aug 24 11:26:26 2007  commencing singleton removal, final pass
Fri Aug 24 11:30:36 2007  memory use: 544.9 MB
Fri Aug 24 11:30:36 2007  commencing in-memory singleton removal
Fri Aug 24 11:30:38 2007  begin with 17577706 relations and 10565419 unique ideals
Fri Aug 24 11:30:53 2007  reduce to 16403746 relations and 9375334 ideals in 8 passes
Fri Aug 24 11:30:53 2007  max relations containing the same ideal: 43
Fri Aug 24 11:31:02 2007  removing 1451017 relations and 1051017 ideals in 400000 cliques
Fri Aug 24 11:31:03 2007  commencing in-memory singleton removal
Fri Aug 24 11:31:05 2007  begin with 14952729 relations and 9375334 unique ideals
Fri Aug 24 11:31:13 2007  reduce to 14912822 relations and 8283479 ideals in 5 passes
Fri Aug 24 11:31:13 2007  max relations containing the same ideal: 40
Fri Aug 24 11:31:22 2007  removing 1162453 relations and 762453 ideals in 400000 cliques
Fri Aug 24 11:31:22 2007  commencing in-memory singleton removal
Fri Aug 24 11:31:24 2007  begin with 13750369 relations and 8283479 unique ideals
Fri Aug 24 11:31:32 2007  reduce to 13724730 relations and 7494862 ideals in 5 passes
Fri Aug 24 11:31:32 2007  max relations containing the same ideal: 37
Fri Aug 24 11:31:39 2007  removing 1036856 relations and 636856 ideals in 400000 cliques
Fri Aug 24 11:31:40 2007  commencing in-memory singleton removal
Fri Aug 24 11:31:42 2007  begin with 12687874 relations and 7494862 unique ideals
Fri Aug 24 11:31:49 2007  reduce to 12651082 relations and 6820241 ideals in 5 passes
Fri Aug 24 11:31:49 2007  max relations containing the same ideal: 36
Fri Aug 24 11:31:56 2007  removing 934697 relations and 534697 ideals in 400000 cliques
Fri Aug 24 11:31:56 2007  commencing in-memory singleton removal
Fri Aug 24 11:31:58 2007  begin with 11716385 relations and 6820241 unique ideals
Fri Aug 24 11:32:03 2007  reduce to 11675134 relations and 6242970 ideals in 4 passes
Fri Aug 24 11:32:03 2007  max relations containing the same ideal: 33
Fri Aug 24 11:32:09 2007  removing 919334 relations and 519334 ideals in 400000 cliques
Fri Aug 24 11:32:10 2007  commencing in-memory singleton removal
Fri Aug 24 11:32:11 2007  begin with 10755800 relations and 6242970 unique ideals
Fri Aug 24 11:32:17 2007  reduce to 10714674 relations and 5681068 ideals in 5 passes
Fri Aug 24 11:32:17 2007  max relations containing the same ideal: 33
Fri Aug 24 11:32:23 2007  removing 900790 relations and 500790 ideals in 400000 cliques
Fri Aug 24 11:32:23 2007  commencing in-memory singleton removal
Fri Aug 24 11:32:24 2007  begin with 9813884 relations and 5681068 unique ideals
Fri Aug 24 11:32:28 2007  reduce to 9774102 relations and 5138950 ideals in 4 passes
Fri Aug 24 11:32:28 2007  max relations containing the same ideal: 30
Fri Aug 24 11:32:34 2007  removing 882840 relations and 482840 ideals in 400000 cliques
Fri Aug 24 11:32:34 2007  commencing in-memory singleton removal
Fri Aug 24 11:32:35 2007  begin with 8891262 relations and 5138950 unique ideals
Fri Aug 24 11:32:40 2007  reduce to 8849181 relations and 4612103 ideals in 5 passes
Fri Aug 24 11:32:40 2007  max relations containing the same ideal: 28
Fri Aug 24 11:32:45 2007  removing 869036 relations and 469036 ideals in 400000 cliques
Fri Aug 24 11:32:45 2007  commencing in-memory singleton removal
Fri Aug 24 11:32:46 2007  begin with 7980145 relations and 4612103 unique ideals
Fri Aug 24 11:32:50 2007  reduce to 7934705 relations and 4095091 ideals in 5 passes
Fri Aug 24 11:32:50 2007  max relations containing the same ideal: 27
Fri Aug 24 11:32:54 2007  removing 857554 relations and 457554 ideals in 400000 cliques
Fri Aug 24 11:32:55 2007  commencing in-memory singleton removal
Fri Aug 24 11:32:56 2007  begin with 7077151 relations and 4095091 unique ideals
Fri Aug 24 11:32:59 2007  reduce to 7026837 relations and 3583941 ideals in 5 passes
Fri Aug 24 11:32:59 2007  max relations containing the same ideal: 26
Fri Aug 24 11:33:03 2007  removing 846989 relations and 446989 ideals in 400000 cliques
Fri Aug 24 11:33:03 2007  commencing in-memory singleton removal
Fri Aug 24 11:33:04 2007  begin with 6179848 relations and 3583941 unique ideals
Fri Aug 24 11:33:06 2007  reduce to 6125142 relations and 3078101 ideals in 4 passes
Fri Aug 24 11:33:06 2007  max relations containing the same ideal: 24
Fri Aug 24 11:33:10 2007  removing 839707 relations and 439707 ideals in 400000 cliques
Fri Aug 24 11:33:10 2007  commencing in-memory singleton removal
Fri Aug 24 11:33:11 2007  begin with 5285435 relations and 3078101 unique ideals
Fri Aug 24 11:33:13 2007  reduce to 5232772 relations and 2581577 ideals in 5 passes
Fri Aug 24 11:33:13 2007  max relations containing the same ideal: 22
Fri Aug 24 11:33:16 2007  removing 843100 relations and 443100 ideals in 400000 cliques
Fri Aug 24 11:33:16 2007  commencing in-memory singleton removal
Fri Aug 24 11:33:16 2007  begin with 4389672 relations and 2581577 unique ideals
Fri Aug 24 11:33:18 2007  reduce to 4335665 relations and 2080537 ideals in 5 passes
Fri Aug 24 11:33:18 2007  max relations containing the same ideal: 19
Fri Aug 24 11:33:21 2007  removing 183513 relations and 112557 ideals in 70956 cliques
Fri Aug 24 11:33:21 2007  commencing in-memory singleton removal
Fri Aug 24 11:33:21 2007  begin with 4152152 relations and 2080537 unique ideals
Fri Aug 24 11:33:23 2007  reduce to 4144302 relations and 1959972 ideals in 5 passes
Fri Aug 24 11:33:23 2007  max relations containing the same ideal: 19
Fri Aug 24 11:33:25 2007  removing 720 relations and 562 ideals in 158 cliques
Fri Aug 24 11:33:25 2007  commencing in-memory singleton removal
Fri Aug 24 11:33:25 2007  begin with 4143582 relations and 1959972 unique ideals
Fri Aug 24 11:33:26 2007  reduce to 4143582 relations and 1959410 ideals in 1 passes
Fri Aug 24 11:33:26 2007  max relations containing the same ideal: 19
Fri Aug 24 11:33:27 2007  dataset has 70.0% excess relations
Fri Aug 24 11:33:32 2007  ignoring smallest 582189 rational and 582351 algebraic ideals
Fri Aug 24 11:33:32 2007  filtering rational ideals above 8675837
Fri Aug 24 11:33:32 2007  filtering algebraic ideals above 8675837
Fri Aug 24 11:33:32 2007  need 1965754 more relations than ideals
Fri Aug 24 11:33:32 2007  commencing singleton removal, final pass
Fri Aug 24 11:35:14 2007  memory use: 116.1 MB
Fri Aug 24 11:35:14 2007  commencing in-memory singleton removal
Fri Aug 24 11:35:15 2007  begin with 4143582 relations and 2079132 unique ideals
Fri Aug 24 11:35:16 2007  reduce to 4140289 relations and 2075833 ideals in 4 passes
Fri Aug 24 11:35:16 2007  max relations containing the same ideal: 39
Fri Aug 24 11:35:17 2007  removing 127477 relations and 78126 ideals in 49351 cliques
Fri Aug 24 11:35:18 2007  commencing in-memory singleton removal
Fri Aug 24 11:35:18 2007  begin with 4012812 relations and 2075833 unique ideals
Fri Aug 24 11:35:19 2007  reduce to 4009695 relations and 1994548 ideals in 4 passes
Fri Aug 24 11:35:19 2007  max relations containing the same ideal: 37
Fri Aug 24 11:35:21 2007  removing 119398 relations and 70047 ideals in 49351 cliques
Fri Aug 24 11:35:21 2007  commencing in-memory singleton removal
Fri Aug 24 11:35:21 2007  begin with 3890297 relations and 1994548 unique ideals
Fri Aug 24 11:35:22 2007  reduce to 3887191 relations and 1921350 ideals in 4 passes
Fri Aug 24 11:35:22 2007  max relations containing the same ideal: 37
Fri Aug 24 11:35:23 2007  dataset has 53.0% excess relations
Fri Aug 24 11:35:28 2007  ignoring smallest 521650 rational and 522014 algebraic ideals
Fri Aug 24 11:35:28 2007  filtering rational ideals above 7711855
Fri Aug 24 11:35:28 2007  filtering algebraic ideals above 7711855
Fri Aug 24 11:35:28 2007  need 1572672 more relations than ideals
Fri Aug 24 11:35:28 2007  commencing singleton removal, final pass
Fri Aug 24 11:37:06 2007  memory use: 116.1 MB
Fri Aug 24 11:37:06 2007  commencing in-memory singleton removal
Fri Aug 24 11:37:07 2007  begin with 3887191 relations and 2041979 unique ideals
Fri Aug 24 11:37:08 2007  reduce to 3885556 relations and 2040343 ideals in 4 passes
Fri Aug 24 11:37:08 2007  max relations containing the same ideal: 40
Fri Aug 24 11:37:10 2007  removing 292555 relations and 156285 ideals in 136270 cliques
Fri Aug 24 11:37:10 2007  commencing in-memory singleton removal
Fri Aug 24 11:37:10 2007  begin with 3593001 relations and 2040343 unique ideals
Fri Aug 24 11:37:12 2007  reduce to 3577323 relations and 1867719 ideals in 5 passes
Fri Aug 24 11:37:12 2007  max relations containing the same ideal: 38
Fri Aug 24 11:37:13 2007  removing 306320 relations and 170050 ideals in 136270 cliques
Fri Aug 24 11:37:13 2007  commencing in-memory singleton removal
Fri Aug 24 11:37:14 2007  begin with 3271003 relations and 1867719 unique ideals
Fri Aug 24 11:37:15 2007  reduce to 3254095 relations and 1679948 ideals in 5 passes
Fri Aug 24 11:37:15 2007  max relations containing the same ideal: 36
Fri Aug 24 11:37:16 2007  removing 5836 relations and 4362 ideals in 1474 cliques
Fri Aug 24 11:37:16 2007  commencing in-memory singleton removal
Fri Aug 24 11:37:17 2007  begin with 3248259 relations and 1679948 unique ideals
Fri Aug 24 11:37:17 2007  reduce to 3248255 relations and 1675582 ideals in 2 passes
Fri Aug 24 11:37:17 2007  max relations containing the same ideal: 36
Fri Aug 24 11:37:18 2007  dataset has 22.4% excess relations
Fri Aug 24 11:37:22 2007  ignoring smallest 460575 rational and 460951 algebraic ideals
Fri Aug 24 11:37:22 2007  filtering rational ideals above 6747873
Fri Aug 24 11:37:22 2007  filtering algebraic ideals above 6747873
Fri Aug 24 11:37:22 2007  need 1387591 more relations than ideals
Fri Aug 24 11:37:22 2007  commencing singleton removal, final pass
Fri Aug 24 11:38:56 2007  memory use: 93.6 MB
Fri Aug 24 11:38:56 2007  commencing in-memory singleton removal
Fri Aug 24 11:38:56 2007  begin with 3248255 relations and 1797592 unique ideals
Fri Aug 24 11:38:57 2007  reduce to 3247084 relations and 1796421 ideals in 4 passes
Fri Aug 24 11:38:57 2007  max relations containing the same ideal: 37
Fri Aug 24 11:38:59 2007  removing 87087 relations and 55551 ideals in 31536 cliques
Fri Aug 24 11:38:59 2007  commencing in-memory singleton removal
Fri Aug 24 11:38:59 2007  begin with 3159997 relations and 1796421 unique ideals
Fri Aug 24 11:39:00 2007  reduce to 3158360 relations and 1739221 ideals in 4 passes
Fri Aug 24 11:39:00 2007  max relations containing the same ideal: 37
Fri Aug 24 11:39:01 2007  removing 81407 relations and 49871 ideals in 31536 cliques
Fri Aug 24 11:39:01 2007  commencing in-memory singleton removal
Fri Aug 24 11:39:02 2007  begin with 3076953 relations and 1739221 unique ideals
Fri Aug 24 11:39:03 2007  reduce to 3075682 relations and 1688067 ideals in 4 passes
Fri Aug 24 11:39:03 2007  max relations containing the same ideal: 37
Fri Aug 24 11:39:03 2007  dataset has 8.0% excess relations
Fri Aug 24 11:39:04 2007  relations with 0 large ideals: 131464
Fri Aug 24 11:39:04 2007  relations with 1 large ideals: 562670
Fri Aug 24 11:39:04 2007  relations with 2 large ideals: 1039939
Fri Aug 24 11:39:04 2007  relations with 3 large ideals: 872447
Fri Aug 24 11:39:04 2007  relations with 4 large ideals: 366605
Fri Aug 24 11:39:04 2007  relations with 5 large ideals: 83162
Fri Aug 24 11:39:04 2007  relations with 6 large ideals: 18599
Fri Aug 24 11:39:04 2007  relations with 7+ large ideals: 796
Fri Aug 24 11:39:04 2007  commencing 2-way merge
Fri Aug 24 11:39:07 2007  merged 643311 relations
Fri Aug 24 11:39:07 2007  reduce to 2432371 relation sets and 1044756 unique ideals
Fri Aug 24 11:39:07 2007  commencing full merge
Fri Aug 24 11:39:47 2007  found 1406861 cycles, need 946726
Fri Aug 24 11:39:48 2007  weight of 946726 cycles is about 56331714 (59.50/cycle)
Fri Aug 24 11:39:48 2007  distribution of cycle lengths:
Fri Aug 24 11:39:48 2007  1 relations: 138525
Fri Aug 24 11:39:48 2007  2 relations: 112429
Fri Aug 24 11:39:48 2007  3 relations: 108696
Fri Aug 24 11:39:48 2007  4 relations: 112669
Fri Aug 24 11:39:48 2007  5 relations: 111291
Fri Aug 24 11:39:48 2007  6 relations: 106205
Fri Aug 24 11:39:48 2007  7 relations: 98609
Fri Aug 24 11:39:48 2007  8 relations: 84869
Fri Aug 24 11:39:48 2007  9 relations: 62233
Fri Aug 24 11:39:48 2007  10+ relations: 11200
Fri Aug 24 11:39:48 2007  heaviest cycle: 12 relations
Fri Aug 24 11:39:48 2007  matrix not dense enough, retrying
Fri Aug 24 11:39:49 2007  dataset has 8.0% excess relations
Fri Aug 24 11:39:53 2007  ignoring smallest 398962 rational and 399013 algebraic ideals
Fri Aug 24 11:39:53 2007  filtering rational ideals above 5783891
Fri Aug 24 11:39:53 2007  filtering algebraic ideals above 5783891
Fri Aug 24 11:39:53 2007  need 1387591 more relations than ideals
Fri Aug 24 11:39:53 2007  commencing singleton removal, final pass
Fri Aug 24 11:41:23 2007  memory use: 116.1 MB
Fri Aug 24 11:41:23 2007  commencing in-memory singleton removal
Fri Aug 24 11:41:23 2007  begin with 3075682 relations and 1811547 unique ideals
Fri Aug 24 11:41:24 2007  reduce to 3075002 relations and 1810867 ideals in 4 passes
Fri Aug 24 11:41:24 2007  max relations containing the same ideal: 38
Fri Aug 24 11:41:24 2007  dataset has -1.6% excess relations
Fri Aug 24 11:41:25 2007  relations with 0 large ideals: 49505
Fri Aug 24 11:41:25 2007  relations with 1 large ideals: 293326
Fri Aug 24 11:41:25 2007  relations with 2 large ideals: 877953
Fri Aug 24 11:41:25 2007  relations with 3 large ideals: 1044483
Fri Aug 24 11:41:25 2007  relations with 4 large ideals: 586920
Fri Aug 24 11:41:25 2007  relations with 5 large ideals: 177740
Fri Aug 24 11:41:25 2007  relations with 6 large ideals: 41818
Fri Aug 24 11:41:25 2007  relations with 7+ large ideals: 3257
Fri Aug 24 11:41:25 2007  commencing 2-way merge
Fri Aug 24 11:42:12 2007  merged 644935 relations
Fri Aug 24 11:42:12 2007  reduce to 2430067 relation sets and 1165932 unique ideals
Fri Aug 24 11:42:12 2007  commencing full merge
Fri Aug 24 11:43:08 2007  found 1350513 cycles, need 890132
Fri Aug 24 11:43:09 2007  weight of 890132 cycles is about 58067886 (65.24/cycle)
Fri Aug 24 11:43:09 2007  distribution of cycle lengths:
Fri Aug 24 11:43:09 2007  1 relations: 83394
Fri Aug 24 11:43:09 2007  2 relations: 96492
Fri Aug 24 11:43:09 2007  3 relations: 97354
Fri Aug 24 11:43:09 2007  4 relations: 107508
Fri Aug 24 11:43:09 2007  5 relations: 107812
Fri Aug 24 11:43:09 2007  6 relations: 107370
Fri Aug 24 11:43:09 2007  7 relations: 100475
Fri Aug 24 11:43:09 2007  8 relations: 90512
Fri Aug 24 11:43:09 2007  9 relations: 71421
Fri Aug 24 11:43:09 2007  10+ relations: 27794
Fri Aug 24 11:43:09 2007  heaviest cycle: 12 relations
Fri Aug 24 11:43:09 2007  commencing cycle optimization
Fri Aug 24 11:43:10 2007  start with 4530830 relations
Fri Aug 24 11:43:22 2007  pruned 194432 relations
Fri Aug 24 11:43:23 2007  distribution of cycle lengths:
Fri Aug 24 11:43:23 2007  1 relations: 83394
Fri Aug 24 11:43:23 2007  2 relations: 99919
Fri Aug 24 11:43:23 2007  3 relations: 105483
Fri Aug 24 11:43:23 2007  4 relations: 115806
Fri Aug 24 11:43:23 2007  5 relations: 118456
Fri Aug 24 11:43:23 2007  6 relations: 115732
Fri Aug 24 11:43:23 2007  7 relations: 103828
Fri Aug 24 11:43:23 2007  8 relations: 82286
Fri Aug 24 11:43:23 2007  9 relations: 50851
Fri Aug 24 11:43:23 2007  10+ relations: 14377
Fri Aug 24 11:43:23 2007  heaviest cycle: 12 relations
Fri Aug 24 11:43:24 2007  
Fri Aug 24 11:43:24 2007  commencing linear algebra
Fri Aug 24 11:43:25 2007  factor base loaded:
Fri Aug 24 11:43:25 2007  695609 rational ideals (max prime = 10499981)
Fri Aug 24 11:43:25 2007  696004 algebraic ideals (max prime = 10499963)
Fri Aug 24 11:43:26 2007  read 890132 cycles
Fri Aug 24 11:43:28 2007  cycles contain 2052489 unique relations
Fri Aug 24 11:45:36 2007  read 2052489 relations
Fri Aug 24 11:45:40 2007  using 32 quadratic characters above 268433330
Fri Aug 24 11:47:47 2007  matrix is 887909 x 890132 with weight 78848393 (avg 88.58/col)
Fri Aug 24 11:48:12 2007  filtering completed in 3 passes
Fri Aug 24 11:48:12 2007  matrix is 867320 x 867520 with weight 77462273 (avg 89.29/col)
Fri Aug 24 11:48:20 2007  saving the first 48 matrix rows for later
Fri Aug 24 11:48:21 2007  matrix is 867272 x 867520 with weight 58581366 (avg 67.53/col)
Fri Aug 24 11:48:21 2007  matrix includes 64 packed rows
Fri Aug 24 11:48:21 2007  using block size 43690 for processor cache size 1024 kB
Fri Aug 24 11:48:24 2007  commencing Lanczos iteration
Fri Aug 24 15:45:59 2007  lanczos halted after 13715 iterations
Fri Aug 24 15:46:03 2007  recovered 46 nontrivial dependencies
Fri Aug 24 15:46:03 2007  
Fri Aug 24 15:46:03 2007  commencing square root phase
Fri Aug 24 15:46:03 2007  reading relations for dependency 1
Fri Aug 24 15:46:04 2007  read 433533 cycles
Fri Aug 24 15:46:05 2007  cycles contain 1233439 unique relations
Fri Aug 24 15:48:01 2007  read 1233439 relations
Fri Aug 24 15:48:11 2007  multiplying 2137304 relations
Fri Aug 24 15:53:07 2007  multiply complete, coefficients have about 56.31 million bits
Fri Aug 24 15:53:09 2007  initial square root is modulo 121291211
Fri Aug 24 16:02:39 2007  reading relations for dependency 2
Fri Aug 24 16:02:41 2007  read 433995 cycles
Fri Aug 24 16:02:42 2007  cycles contain 1234256 unique relations
Fri Aug 24 16:04:12 2007  read 1234256 relations
Fri Aug 24 16:04:22 2007  multiplying 2140280 relations
Fri Aug 24 16:09:20 2007  multiply complete, coefficients have about 56.38 million bits
Fri Aug 24 16:09:21 2007  initial square root is modulo 124444211
Fri Aug 24 16:18:52 2007  reading relations for dependency 3
Fri Aug 24 16:18:53 2007  read 433541 cycles
Fri Aug 24 16:18:54 2007  cycles contain 1233910 unique relations
Fri Aug 24 16:20:22 2007  read 1233910 relations
Fri Aug 24 16:20:31 2007  multiplying 2138418 relations
Fri Aug 24 16:25:28 2007  multiply complete, coefficients have about 56.34 million bits
Fri Aug 24 16:25:30 2007  initial square root is modulo 122477111
Fri Aug 24 16:35:00 2007  reading relations for dependency 4
Fri Aug 24 16:35:01 2007  read 434542 cycles
Fri Aug 24 16:35:02 2007  cycles contain 1236700 unique relations
Fri Aug 24 16:36:31 2007  read 1236700 relations
Fri Aug 24 16:36:40 2007  multiplying 2145084 relations
Fri Aug 24 16:41:36 2007  multiply complete, coefficients have about 56.51 million bits
Fri Aug 24 16:41:38 2007  initial square root is modulo 129892181
Fri Aug 24 16:51:19 2007  prp64 factor: 2238238060593160915154908233503446000454760852236311947179566373
Fri Aug 24 16:51:19 2007  prp82 factor: 2226305073213122705441817017885625244261473939652907905385454502100968447707427177
Fri Aug 24 16:51:19 2007  elapsed time 05:52:15

In particular, note the line

Fri Aug 24 11:41:24 2007 dataset has -1.6% excess relations

The case was VERY oversieved, and it did finish successfully.

Greg

[jasonp]

Originally Posted by satfreak666

make: *** [generic] Error 1

On OS X Intel with gcc, you have to compile with 'make x86'

[jasonp]

Originally Posted by frmky

In particular, note the line

Fri Aug 24 11:41:24 2007 dataset has -1.6% excess relations

The case was VERY oversieved, and it did finish successfully.

The filtering will try to get 8% excess relations and then moves to the merge phase. When merging completes, if the matrix is too sparse (as is the case here), the collection of merged relations is thrown away and the filtering is repeated with a more stringent bound. I had to add this tweak after several factorizations failed in the linear algebra stage, probably because the matrix was too sparse.

The log message above means that technically you do not have enough excess to construct a matrix, but the code thinks that because the number of cycles is estimated as (num_relations - num_unique_ideals), and the actual number of possible cycles exceeds that. When you've oversieved by a lot, the estimate is inaccurate and you have to use the sparsity in the actual matrix to determine whether to keep pushing the matrix size downwards.

[Chris Card]

Originally Posted by jasonp

I had to add this tweak after several factorizations failed in the linear algebra stage, probably because the matrix was too sparse.

Why does the sparseness of the matrix affect the chances of finding a non-trivial dependency? I thought that as long as you had enough relations then the chance of a dependency being non-trivial was roughly 50%.

Chris

[jasonp]

Originally Posted by Chris Card

Why does the sparseness of the matrix affect the chances of finding a non-trivial dependency? I thought that as long as you had enough relations then the chance of a dependency being non-trivial was roughly 50%.

I thought so too, but with the output from msieve filtering, sometimes people fail to get nontrivial dependencies when the input matrix is too sparse, independent of the random starting vector. It's never happened when the matrix has more than 65 nonzeros per column on average, so the code pushes for that. In fact, Tom Womack sent me relations for two big and heavily oversieved factorizations where you cannot get nontrivial dependencies unless you push the matrix density up *and* delete empty rows, singletons and cliques in the matrix before running the Lanczos solver.

QS never suffered from this problem, even though QS with one large prime generates matrices with ~15 nonzeros per column all the time. I do sometimes see reports on the GGNFS mailing list that the GGNFS lanczos solver also fails to find nontrivial dependencies, but I don't think the matrices involved were overly sparse. Early on, QS generated matrices where the solver would fail unless empty and singleton rows were deleted before running the solver.

It could be a bug in the filtering, or in the solver. The two are as independent as possible in order to cross-check each other. If the behavior is actually an expected byproduct of the Lanczos algorithm, then my guess is that it's because Lanczos does not solve the input linear system but solves a symmetrized version of it, and when there is too much matrix excess or the matrix is too sparse then the nullspace of the symmetrized matrix is too different from that of the input matrix to derive nullspace vectors for the latter. Anecdotally, the CWI matrix solver also sometimes doesn't work if there are too many excess columns (Bob / Paul, correct me if I'm wrong).

To make a long story short, I originally didn't think any of this mattered, but in the face of experimental evidence to the contrary I've added voodoo to msieve.

[xilman]

Originally Posted by jasonp

Anecdotally, the CWI matrix solver also sometimes doesn't work if there are too many excess columns (Bob / Paul, correct me if I'm wrong).

You're correct.

No-one seems to know why this phenomenon occurs, but it undoubtedly does and it does so in several independently developed implementations.

Paul