Msieve with GNFS support

[jasonp]

Originally Posted by fivemack

This is a C136, ~28 million input relations sieved with fb=9000000 lp=2^29
[...]
When I rerun with gdb, it seems that the problem is at line 431 of gnfs/gf2.c

dense_rows[idx/32] |= 1<<(idx%32)

So it's trying to handle a dense ideal which isn't in the table of small ideals. I'm happy to run more tests if you suggest what to run ...

v1.21 already includes a fix for a problem like this. If your factor base was generated with an earlier msieve version then try regenerating it with v1.21; otherwise if you could compile with -O0 and email me the gdb output of 'bt full' at the crash point then I'd be grateful. I'll have to put exit-gracefully code at this point, at least three bugs in the factor base generator have caused crashes there.

jasonp

[smh]

Originally Posted by jasonp

....I want to try some more really big NFS jobs....

What do you consider big (both GNFS and SNFS).

[smh]

Originally Posted by jasonp

Sander, the runs that are giving me problems include a C129 and C136 via GNFS, and a C200 vis SNFS.

I think I'll be able to sieve a ~c130 in a reasonable amount of time.
Any suggestion for interesting numbers around this size that have had enough ECM?

[Andi47]

Originally Posted by smh

I think I'll be able to sieve a ~c130 in a reasonable amount of time.
Any suggestion for interesting numbers around this size that have had enough ECM?

You can take for example one of the Homogeneous Cunningham Numbers, there are still some unresearved c130's.

[fivemack]

Originally Posted by jasonp

Andi,

v1.22 has a few small multithreading improvements and bug fixes compared to the alpha version I posted, I'd recommend switching to it.

Sander, the runs that are giving me problems include a C129 and C136 via GNFS, and a C200 vis SNFS.

Thanks very much for v1.22; it's managed to handle, on the first dependency, a C121 for which ggnfs had produced a matrix all of whose dependencies led to the trivial factorisation.

In about a week I'll have finished sieving the C138 cofactor of fibonacci(1171), and can see how v1.22 works on that. The large-prime bound is only 2^28 for this one, so the relations ought to fit compressed on only one DVD if I end up having to send them out for further study

[Andi47]

Originally Posted by Andi47

Did you change anything in saving the relations between versions 1.21 and 1.22alpha? During filtering it gave a series of error -14 and one error-3 reading certain relations (totals to 55 bad relations):

1.22 logfile reads:

Sun May 27 20:25:05 2007  Msieve v. 1.22
Sun May 27 20:25:05 2007  random seeds: 551b5afc 85b4f970
Sun May 27 20:25:05 2007  factoring 59851368441126867505175036119618017965374014823386475353855554519233951829509128116614500240090827807 (101 digits)
Sun May 27 20:25:05 2007  commencing number field sieve (101-digit input)
Sun May 27 20:25:05 2007  R0: -175286939562562530
Sun May 27 20:25:05 2007  R1:  1
Sun May 27 20:25:05 2007  A0:  2954919142613807
Sun May 27 20:25:05 2007  A1: -3053237587397760
Sun May 27 20:25:05 2007  A2:  2379165919791292
Sun May 27 20:25:05 2007  A3:  2488888495499642
Sun May 27 20:25:05 2007  A4: -2775280927915645
Sun May 27 20:25:05 2007  A5:  361681497428832
Sun May 27 20:25:05 2007  size score = 1.031788e-010, Murphy alpha = -2.650199, combined = 2.496008e-010
Sun May 27 20:25:15 2007  restarting with 4046282 relations
Sun May 27 20:25:15 2007  
Sun May 27 20:25:15 2007  commencing relation filtering
Sun May 27 20:25:15 2007  commencing duplicate removal, pass 1
Sun May 27 20:25:19 2007  error -14 reading relation 419584
Sun May 27 20:25:20 2007  error -14 reading relation 448609
Sun May 27 20:25:20 2007  error -14 reading relation 504209
Sun May 27 20:25:22 2007  error -14 reading relation 627685
Sun May 27 20:25:22 2007  error -14 reading relation 648897
Sun May 27 20:25:22 2007  error -14 reading relation 671884
Sun May 27 20:25:23 2007  error -14 reading relation 723819
Sun May 27 20:25:24 2007  error -14 reading relation 830715
Sun May 27 20:25:26 2007  error -14 reading relation 1020917
Sun May 27 20:25:26 2007  error -14 reading relation 1020968
Sun May 27 20:25:26 2007  error -14 reading relation 1068758
Sun May 27 20:25:27 2007  error -14 reading relation 1111589
Sun May 27 20:25:27 2007  error -14 reading relation 1148791
Sun May 27 20:25:28 2007  error -14 reading relation 1220163
Sun May 27 20:25:29 2007  error -14 reading relation 1291952
Sun May 27 20:25:29 2007  error -14 reading relation 1297280
Sun May 27 20:25:29 2007  error -14 reading relation 1313716
Sun May 27 20:25:30 2007  error -14 reading relation 1403724
Sun May 27 20:25:32 2007  error -14 reading relation 1534919
Sun May 27 20:25:33 2007  error -14 reading relation 1658666
Sun May 27 20:25:33 2007  error -14 reading relation 1675327
Sun May 27 20:25:33 2007  error -14 reading relation 1679435
Sun May 27 20:25:35 2007  error -14 reading relation 1793328
Sun May 27 20:25:35 2007  error -14 reading relation 1845937
Sun May 27 20:25:36 2007  error -14 reading relation 1944811
Sun May 27 20:25:37 2007  error -14 reading relation 2033707
Sun May 27 20:25:37 2007  error -14 reading relation 2042483
Sun May 27 20:25:39 2007  error -14 reading relation 2166831
Sun May 27 20:25:39 2007  error -14 reading relation 2167315
Sun May 27 20:25:40 2007  error -14 reading relation 2243282
Sun May 27 20:25:40 2007  error -14 reading relation 2266643
Sun May 27 20:25:42 2007  error -14 reading relation 2454429
Sun May 27 20:25:42 2007  error -14 reading relation 2461537
Sun May 27 20:25:43 2007  error -14 reading relation 2529520
Sun May 27 20:25:44 2007  error -14 reading relation 2578890
Sun May 27 20:25:44 2007  error -14 reading relation 2654189
Sun May 27 20:25:45 2007  error -14 reading relation 2679930
Sun May 27 20:25:45 2007  error -14 reading relation 2731679
Sun May 27 20:25:46 2007  error -14 reading relation 2766503
Sun May 27 20:25:46 2007  error -14 reading relation 2789851
Sun May 27 20:25:46 2007  error -14 reading relation 2819985
Sun May 27 20:25:48 2007  error -14 reading relation 2928619
Sun May 27 20:25:49 2007  error -14 reading relation 3053936
Sun May 27 20:25:49 2007  error -14 reading relation 3071780
Sun May 27 20:25:49 2007  error -14 reading relation 3090392
Sun May 27 20:25:50 2007  error -14 reading relation 3142467
Sun May 27 20:25:52 2007  error -14 reading relation 3346153
Sun May 27 20:25:54 2007  error -14 reading relation 3461292
Sun May 27 20:25:54 2007  error -14 reading relation 3466881
Sun May 27 20:25:55 2007  error -14 reading relation 3546257
Sun May 27 20:25:57 2007  error -3 reading relation 3723754
Sun May 27 20:25:58 2007  error -14 reading relation 3803670
Sun May 27 20:25:58 2007  error -14 reading relation 3833701
Sun May 27 20:25:59 2007  error -14 reading relation 3949808
Sun May 27 20:26:00 2007  error -14 reading relation 3988410
Sun May 27 20:26:01 2007  found 30395 hash collisions in 4046227 relations
Sun May 27 20:26:01 2007  commencing duplicate removal, pass 2
Sun May 27 20:26:11 2007  found 0 duplicates and 4046227 unique relations
Sun May 27 20:26:11 2007  memory use: 36.9 MB
Sun May 27 20:26:13 2007  ignoring smallest 192370 rational and 192563 algebraic ideals
Sun May 27 20:26:13 2007  filtering rational ideals above 2637001
Sun May 27 20:26:13 2007  filtering algebraic ideals above 2637001
Sun May 27 20:26:13 2007  need 654386 more relations than ideals
Sun May 27 20:26:13 2007  commencing singleton removal, pass 1
Sun May 27 20:27:02 2007  relations with 0 large ideals: 75333
Sun May 27 20:27:02 2007  relations with 1 large ideals: 562834
Sun May 27 20:27:02 2007  relations with 2 large ideals: 1467911
Sun May 27 20:27:02 2007  relations with 3 large ideals: 1487681
Sun May 27 20:27:02 2007  relations with 4 large ideals: 452468
Sun May 27 20:27:02 2007  relations with 5 large ideals: 0
Sun May 27 20:27:02 2007  relations with 6 large ideals: 0
Sun May 27 20:27:02 2007  relations with 7+ large ideals: 0
Sun May 27 20:27:02 2007  4046227 relations and about 4127707 large ideals
Sun May 27 20:27:02 2007  commencing singleton removal, pass 2
Sun May 27 20:27:51 2007  found 1957308 singletons
Sun May 27 20:27:51 2007  current dataset: 2088919 relations and about 1773326 large ideals
Sun May 27 20:27:51 2007  commencing singleton removal, pass 3
Sun May 27 20:28:18 2007  found 449611 singletons
Sun May 27 20:28:18 2007  current dataset: 1639308 relations and about 1283469 large ideals
Sun May 27 20:28:18 2007  commencing singleton removal, pass 4
Sun May 27 20:28:41 2007  found 153521 singletons
Sun May 27 20:28:41 2007  current dataset: 1485787 relations and about 1124104 large ideals
Sun May 27 20:28:41 2007  commencing singleton removal, pass 5
Sun May 27 20:29:02 2007  found 58431 singletons
Sun May 27 20:29:02 2007  current dataset: 1427356 relations and about 1064746 large ideals
Sun May 27 20:29:02 2007  commencing singleton removal, final pass
Sun May 27 20:29:22 2007  memory use: 51.4 MB
Sun May 27 20:29:22 2007  commencing in-memory singleton removal
Sun May 27 20:29:22 2007  begin with 1427356 relations and 1095471 unique ideals
Sun May 27 20:29:24 2007  reduce to 1283849 relations and 950054 ideals in 14 passes
Sun May 27 20:29:24 2007  max relations containing the same ideal: 14
Sun May 27 20:29:24 2007  filtering wants 961773 more relations
Sun May 27 20:29:24 2007  factor base loaded:
Sun May 27 20:29:24 2007  158623 rational ideals (max prime = 2140907)
Sun May 27 20:29:24 2007  158670 algebraic ideals (max prime = 2140877)
Sun May 27 20:29:24 2007  a range: [-6727274, 6727273]
Sun May 27 20:29:24 2007  b range: [638447, 4294967295]
Sun May 27 20:29:24 2007  number of hash buckets: 33
Sun May 27 20:29:24 2007  sieve block size: 65536
Sun May 27 20:29:24 2007  
Sun May 27 20:29:24 2007  maximum RFB prime: 2140907
Sun May 27 20:29:24 2007  RFB entries: 158623
Sun May 27 20:29:24 2007  medium RFB entries: 6542
Sun May 27 20:29:24 2007  resieved RFB entries: 6374
Sun May 27 20:29:24 2007  small RFB prime powers: 28
Sun May 27 20:29:24 2007  projective RFB roots: 0
Sun May 27 20:29:24 2007  RFB trial factoring cutoff: 55 bits
Sun May 27 20:29:24 2007  single large prime RFB range: 21 - 26 bits
Sun May 27 20:29:24 2007  double large prime RFB range: 43 - 50 bits
Sun May 27 20:29:24 2007  
Sun May 27 20:29:24 2007  maximum AFB prime: 2140877
Sun May 27 20:29:24 2007  AFB entries: 158670
Sun May 27 20:29:24 2007  medium AFB entries: 6534
Sun May 27 20:29:24 2007  resieved AFB entries: 6339
Sun May 27 20:29:24 2007  small AFB prime powers: 43
Sun May 27 20:29:24 2007  projective AFB roots: 8
Sun May 27 20:29:24 2007  AFB trial factoring cutoff: 55 bits
Sun May 27 20:29:24 2007  single large prime AFB range: 21 - 26 bits
Sun May 27 20:29:24 2007  double large prime AFB range: 43 - 50 bits
Sun May 27 20:29:24 2007

edit: my run on a c103 which has been started with 1.22alpha does not show such errors, but some of the "bad" relations with the c101 have been found with 1.22alpha.

With enough relations (4.9M) the linear algebra succeeded anyway.

[jasonp]

Originally Posted by fivemack

Thanks very much for v1.22; it's managed to handle, on the first dependency, a C121 for which ggnfs had produced a matrix all of whose dependencies led to the trivial factorisation.

In about a week I'll have finished sieving the C138 cofactor of fibonacci(1171), and can see how v1.22 works on that. The large-prime bound is only 2^28 for this one, so the relations ought to fit compressed on only one DVD if I end up having to send them out for further study

Good to hear. I've made changes to the filtering and linear algebra so that the two factorizations whose relations you mailed work a lot better. The C136 completes now, and I'm running the linear algebra on the C200 (it should finish tomorrow morning). Probably v1.23 will be out this week. As long as folks keep pounding on the code I think I can sustain a two-week release schedule. There are still some filtering tweaks I want to implement; singleton removal for the C200 needs a lot of work.

Andi, congrats on finishing. Other people have reported the -14 errors and I'm investigating. My guess is that your old factor base had a mistaken entry or two, which the new code caught.

Greg, your timings match with my experience; the matrix multiply is a serious bandwidth hog and to get decent performance you need separate memory buses and/or separate memory controllers.

[frmky]

Hi,

Here's an odd problem for ya. I had the following messed up line in my relations file:

-20785806,9328253:3467459,BCD5,2B6F3,24794F,3E9147,7,2B,107,115,3,3,CF2365:489DF,1-1578517,2657041:c622985,268F,17419,1F6FF,48647,3158F9,7,7,1D,BF,115,79D:2A653,29CA5F,40644D,13,2B3,455,C53855

It's obviously due to a truncation of one line, followed by the beginning of a second. The problem is that when msieve tried to read it, it got stuck in what seemed to be an infinite loop. Tracking this down in a 1.8 GB file was fun.

Greg

[jasonp]

Originally Posted by frmky

Hi,

Here's an odd problem for ya. I had the following messed up line in my relations file:

-20785806,9328253:3467459,BCD5,2B6F3,24794F,3E9147,7,2B,107,115,3,3,CF2365:489DF,1-1578517,2657041:c622985,268F,17419,1F6FF,48647,3158F9,7,7,1D,BF,115,79D:2A653,29CA5F,40644D,13,2B3,455,C53855

It's obviously due to a truncation of one line, followed by the beginning of a second. The problem is that when msieve tried to read it, it got stuck in what seemed to be an infinite loop. Tracking this down in a 1.8 GB file was fun.

Greg

Grr. On line 149 and 182 of gnfs/relation.c, change 'p > 0' to 'p > 1'.
Sorry about that.

[fivemack]

I am happy to announce that the two largest prime factors of Fibonacci(1171) are

25153581475807469712135476776559283080497468613537 * 
8819430499963616520071269821480424979203481406180373830145260754015654908007706407494709;

60hrs polynomial selection to get something with Murphy score 27.6e-12, 750 CPU-hours sieving (small primes up to 9e6, large primes up to 2^28) over a week or so on two dual-core machines to get 14.1 million unique relations. msieve-1.23 made a 1274168 x 1274368 matrix of weight 121993547, found 46 dependencies in 4.5 hours, and found the factorisation by the second square root at about 1 hour per square root.

Thu Jun  7 18:18:41 2007  Msieve v. 1.23
Thu Jun  7 18:18:41 2007  random seeds: 7b50b399 7b656c67
Thu Jun  7 18:18:41 2007  factoring 221840263651056235680273123718480662435937616449528078970707629219414458837009436764502600624153262012774907167977202918671464031893275733 (138 digits)
Thu Jun  7 18:18:41 2007  commencing number field sieve (138-digit input)
Thu Jun  7 18:18:41 2007  R0: -164782834457696999659258797
Thu Jun  7 18:18:41 2007  R1:  602677220572189
Thu Jun  7 18:18:41 2007  A0:  3708113580868439915816551655000
Thu Jun  7 18:18:41 2007  A1: -743087353888679016690286804
Thu Jun  7 18:18:41 2007  A2:  9811725974858749340042
Thu Jun  7 18:18:41 2007  A3: -72578909033029131
Thu Jun  7 18:18:41 2007  A4: -1399819005162
Thu Jun  7 18:18:41 2007  A5:  1825920
Thu Jun  7 18:18:41 2007  size score = 3.136677e-14, Murphy alpha = -6.190813, combined = 2.469914e-13
Thu Jun  7 18:19:20 2007  restarting with 17835696 relations
Thu Jun  7 18:19:20 2007  generating factor base
Thu Jun  7 18:19:23 2007  factor base complete:
Thu Jun  7 18:19:23 2007  441562 rational roots (max prime = 6449923)
Thu Jun  7 18:19:23 2007  441688 algebraic roots (max prime = 6449923)
Thu Jun  7 18:19:24 2007  added 3658 free relations
Thu Jun  7 18:19:24 2007  
Thu Jun  7 18:19:24 2007  commencing relation filtering
Thu Jun  7 18:19:24 2007  commencing duplicate removal, pass 1
Thu Jun  7 18:22:55 2007  error -3 reading relation 17835696
Thu Jun  7 18:22:55 2007  found 4146010 hash collisions in 17839353 relations
Thu Jun  7 18:22:55 2007  commencing duplicate removal, pass 2
Thu Jun  7 18:23:43 2007  found 3784139 duplicates and 14055214 unique relations
Thu Jun  7 18:23:43 2007  memory use: 94.6 MB
Thu Jun  7 18:23:48 2007  ignoring smallest 505682 rational and 506141 algebraic ideals
Thu Jun  7 18:23:48 2007  filtering rational ideals above 7458661
Thu Jun  7 18:23:48 2007  filtering algebraic ideals above 7458661
Thu Jun  7 18:23:48 2007  need 1720099 more relations than ideals
Thu Jun  7 18:23:48 2007  commencing singleton removal, pass 1
Thu Jun  7 18:25:53 2007  relations with 0 large ideals: 105742
Thu Jun  7 18:25:53 2007  relations with 1 large ideals: 987531
Thu Jun  7 18:25:53 2007  relations with 2 large ideals: 3281630
Thu Jun  7 18:25:53 2007  relations with 3 large ideals: 4850545
Thu Jun  7 18:25:53 2007  relations with 4 large ideals: 3534021
Thu Jun  7 18:25:53 2007  relations with 5 large ideals: 1153138
Thu Jun  7 18:25:53 2007  relations with 6 large ideals: 134638
Thu Jun  7 18:25:53 2007  relations with 7+ large ideals: 7969
Thu Jun  7 18:25:53 2007  14055214 relations and about 12976360 large ideals
Thu Jun  7 18:25:53 2007  commencing singleton removal, pass 2
Thu Jun  7 18:28:41 2007  found 6085204 singletons
Thu Jun  7 18:28:41 2007  current dataset: 7970010 relations and about 5995566 large ideals
Thu Jun  7 18:28:41 2007  commencing singleton removal, pass 3
Thu Jun  7 18:30:38 2007  found 894501 singletons
Thu Jun  7 18:30:38 2007  current dataset: 7075509 relations and about 5066411 large ideals
Thu Jun  7 18:30:38 2007  commencing singleton removal, pass 4
Thu Jun  7 18:31:51 2007  found 178267 singletons
Thu Jun  7 18:31:51 2007  current dataset: 6897242 relations and about 4886513 large ideals
Thu Jun  7 18:31:51 2007  commencing singleton removal, final pass
Thu Jun  7 18:33:04 2007  memory use: 279.6 MB
Thu Jun  7 18:33:04 2007  commencing in-memory singleton removal
Thu Jun  7 18:33:05 2007  begin with 6897242 relations and 5333809 unique ideals
Thu Jun  7 18:33:11 2007  reduce to 6036519 relations and 4454460 ideals in 10 passes
Thu Jun  7 18:33:11 2007  max relations containing the same ideal: 37
Thu Jun  7 18:33:12 2007  dataset has 56.4% excess relations
Thu Jun  7 18:33:15 2007  ignoring smallest 458328 rational and 458480 algebraic ideals
Thu Jun  7 18:33:15 2007  filtering rational ideals above 6712794
Thu Jun  7 18:33:15 2007  filtering algebraic ideals above 6712794
Thu Jun  7 18:33:15 2007  need 1423853 more relations than ideals
Thu Jun  7 18:33:15 2007  commencing singleton removal, final pass
Thu Jun  7 18:34:36 2007  memory use: 279.6 MB
Thu Jun  7 18:34:36 2007  commencing in-memory singleton removal
Thu Jun  7 18:34:37 2007  begin with 6897242 relations and 5428797 unique ideals
Thu Jun  7 18:34:46 2007  reduce to 6035770 relations and 4548675 ideals in 11 passes
Thu Jun  7 18:34:46 2007  max relations containing the same ideal: 39
Thu Jun  7 18:34:50 2007  removing 251436 relations and 219815 ideals in 31621 cliques
Thu Jun  7 18:34:50 2007  commencing in-memory singleton removal
Thu Jun  7 18:34:51 2007  begin with 5784334 relations and 4548675 unique ideals
Thu Jun  7 18:34:55 2007  reduce to 5779527 relations and 4324028 ideals in 6 passes
Thu Jun  7 18:34:55 2007  max relations containing the same ideal: 37
Thu Jun  7 18:34:59 2007  removing 190712 relations and 159091 ideals in 31621 cliques
Thu Jun  7 18:34:59 2007  commencing in-memory singleton removal
Thu Jun  7 18:35:00 2007  begin with 5588815 relations and 4324028 unique ideals
Thu Jun  7 18:35:05 2007  reduce to 5585622 relations and 4161723 ideals in 6 passes
Thu Jun  7 18:35:05 2007  max relations containing the same ideal: 36
Thu Jun  7 18:35:06 2007  dataset has 40.7% excess relations
Thu Jun  7 18:35:09 2007  ignoring smallest 410759 rational and 410944 algebraic ideals
Thu Jun  7 18:35:09 2007  filtering rational ideals above 5966928
Thu Jun  7 18:35:09 2007  filtering algebraic ideals above 5966928
Thu Jun  7 18:35:09 2007  need 1139119 more relations than ideals
Thu Jun  7 18:35:09 2007  commencing singleton removal, final pass
Thu Jun  7 18:36:19 2007  memory use: 221.0 MB
Thu Jun  7 18:36:19 2007  commencing in-memory singleton removal
Thu Jun  7 18:36:20 2007  begin with 5585622 relations and 4256790 unique ideals
Thu Jun  7 18:36:24 2007  reduce to 5584995 relations and 4256163 ideals in 5 passes
Thu Jun  7 18:36:24 2007  max relations containing the same ideal: 37
Thu Jun  7 18:36:28 2007  removing 451941 relations and 357085 ideals in 94856 cliques
Thu Jun  7 18:36:29 2007  commencing in-memory singleton removal
Thu Jun  7 18:36:29 2007  begin with 5133054 relations and 4256163 unique ideals
Thu Jun  7 18:36:34 2007  reduce to 5114059 relations and 3879779 ideals in 6 passes
Thu Jun  7 18:36:34 2007  max relations containing the same ideal: 33
Thu Jun  7 18:36:38 2007  removing 409239 relations and 314383 ideals in 94856 cliques
Thu Jun  7 18:36:39 2007  commencing in-memory singleton removal
Thu Jun  7 18:36:39 2007  begin with 4704820 relations and 3879779 unique ideals
Thu Jun  7 18:36:43 2007  reduce to 4686691 relations and 3546969 ideals in 7 passes
Thu Jun  7 18:36:43 2007  max relations containing the same ideal: 32
Thu Jun  7 18:36:47 2007  removing 4908 relations and 4306 ideals in 602 cliques
Thu Jun  7 18:36:47 2007  commencing in-memory singleton removal
Thu Jun  7 18:36:47 2007  begin with 4681783 relations and 3546969 unique ideals
Thu Jun  7 18:36:49 2007  reduce to 4681779 relations and 3542659 ideals in 3 passes
Thu Jun  7 18:36:49 2007  max relations containing the same ideal: 31
Thu Jun  7 18:36:50 2007  dataset has 12.6% excess relations
Thu Jun  7 18:36:52 2007  ignoring smallest 362790 rational and 362689 algebraic ideals
Thu Jun  7 18:36:52 2007  filtering rational ideals above 5221062
Thu Jun  7 18:36:52 2007  filtering algebraic ideals above 5221062
Thu Jun  7 18:36:52 2007  need 1092768 more relations than ideals
Thu Jun  7 18:36:52 2007  commencing singleton removal, final pass
Thu Jun  7 18:38:07 2007  memory use: 176.9 MB
Thu Jun  7 18:38:07 2007  commencing in-memory singleton removal
Thu Jun  7 18:38:08 2007  begin with 4681779 relations and 3638832 unique ideals
Thu Jun  7 18:38:11 2007  reduce to 4681122 relations and 3638175 ideals in 4 passes
Thu Jun  7 18:38:11 2007  max relations containing the same ideal: 36
Thu Jun  7 18:38:12 2007  dataset has 3.1% excess relations
Thu Jun  7 18:38:14 2007  relations with 0 large ideals: 33877
Thu Jun  7 18:38:14 2007  relations with 1 large ideals: 259382
Thu Jun  7 18:38:14 2007  relations with 2 large ideals: 854118
Thu Jun  7 18:38:14 2007  relations with 3 large ideals: 1432037
Thu Jun  7 18:38:14 2007  relations with 4 large ideals: 1292100
Thu Jun  7 18:38:14 2007  relations with 5 large ideals: 623777
Thu Jun  7 18:38:14 2007  relations with 6 large ideals: 160572
Thu Jun  7 18:38:14 2007  relations with 7+ large ideals: 25259
Thu Jun  7 18:38:14 2007  commencing 2-way merge
Thu Jun  7 18:38:17 2007  merged 1541249 relations
Thu Jun  7 18:38:19 2007  reduce to 3139873 relation sets and 2096926 unique ideals
Thu Jun  7 18:38:19 2007  commencing full merge
Thu Jun  7 18:42:47 2007  found 1602922 cycles, need 1287126
Thu Jun  7 18:42:49 2007  weight of 1287126 cycles is about 83757268 (65.07/cycle)
Thu Jun  7 18:42:49 2007  distribution of cycle lengths:
Thu Jun  7 18:42:49 2007  1 relations: 147123
Thu Jun  7 18:42:49 2007  2 relations: 155143
Thu Jun  7 18:42:49 2007  3 relations: 164001
Thu Jun  7 18:42:49 2007  4 relations: 159088
Thu Jun  7 18:42:49 2007  5 relations: 150861
Thu Jun  7 18:42:49 2007  6 relations: 137280
Thu Jun  7 18:42:49 2007  7 relations: 121676
Thu Jun  7 18:42:49 2007  8 relations: 105293
Thu Jun  7 18:42:49 2007  9 relations: 86608
Thu Jun  7 18:42:49 2007  10+ relations: 60053
Thu Jun  7 18:42:49 2007  heaviest cycle: 12 relations
Thu Jun  7 18:42:49 2007  commencing cycle optimization
Thu Jun  7 18:44:33 2007  start with 6240874 relations
Thu Jun  7 18:44:58 2007  pruned 109353 relations
Thu Jun  7 18:44:59 2007  distribution of cycle lengths:
Thu Jun  7 18:44:59 2007  1 relations: 147123
Thu Jun  7 18:44:59 2007  2 relations: 157464
Thu Jun  7 18:44:59 2007  3 relations: 168704
Thu Jun  7 18:44:59 2007  4 relations: 162760
Thu Jun  7 18:44:59 2007  5 relations: 155784
Thu Jun  7 18:44:59 2007  6 relations: 140699
Thu Jun  7 18:44:59 2007  7 relations: 123917
Thu Jun  7 18:44:59 2007  8 relations: 103736
Thu Jun  7 18:44:59 2007  9 relations: 79749
Thu Jun  7 18:44:59 2007  10+ relations: 47190
Thu Jun  7 18:44:59 2007  heaviest cycle: 12 relations
Thu Jun  7 18:45:00 2007  
Thu Jun  7 18:45:01 2007  commencing linear algebra
Thu Jun  7 18:45:02 2007  factor base loaded:
Thu Jun  7 18:45:02 2007  441562 rational ideals (max prime = 6449923)
Thu Jun  7 18:45:02 2007  441688 algebraic ideals (max prime = 6449923)
Thu Jun  7 18:45:46 2007  read 1287126 cycles
Thu Jun  7 18:45:53 2007  cycles contain 3555775 unique relations
Thu Jun  7 18:46:39 2007  read 3555775 relations
Thu Jun  7 18:46:45 2007  using 32 quadratic characters above 268432422
Thu Jun  7 18:50:25 2007  matrix is 1286040 x 1287126 with weight 122946574 (avg 95.52/col)
Thu Jun  7 18:51:03 2007  filtering completed in 3 passes
Thu Jun  7 18:51:03 2007  matrix is 1274168 x 1274368 with weight 121993547 (avg 95.73/col)
Thu Jun  7 18:51:37 2007  saving the first 48 matrix rows for later
Thu Jun  7 18:51:39 2007  matrix is 1274120 x 1274368 with weight 94043789 (avg 73.80/col)
Thu Jun  7 18:51:39 2007  matrix includes 64 packed rows
Thu Jun  7 18:51:39 2007  using block size 65536 for processor cache size 4096 kB
Thu Jun  7 18:54:52 2007  commencing Lanczos iteration
Thu Jun  7 23:19:50 2007  lanczos halted after 20153 iterations
Thu Jun  7 23:19:53 2007  recovered 46 nontrivial dependencies
Thu Jun  7 23:19:53 2007  
Thu Jun  7 23:19:53 2007  commencing square root phase
Thu Jun  7 23:19:53 2007  reading relations for dependency 1
Thu Jun  7 23:19:54 2007  read 637380 cycles
Thu Jun  7 23:19:57 2007  cycles contain 2132964 unique relations
Thu Jun  7 23:20:33 2007  read 2132964 relations
Thu Jun  7 23:20:46 2007  multiplying 3047868 relations
Thu Jun  7 23:47:15 2007  multiply complete, coefficients have about 164.52 million bits
Thu Jun  7 23:47:28 2007  initial square root is modulo 802583
Fri Jun  8 00:17:12 2007  reading relations for dependency 2
Fri Jun  8 00:17:13 2007  read 636458 cycles
Fri Jun  8 00:17:18 2007  cycles contain 2132459 unique relations
Fri Jun  8 00:18:25 2007  read 2132459 relations
Fri Jun  8 00:18:47 2007  multiplying 3046244 relations
Fri Jun  8 01:01:54 2007  multiply complete, coefficients have about 164.44 million bits
Fri Jun  8 01:02:03 2007  initial square root is modulo 796673
Fri Jun  8 01:29:39 2007  prp50 factor: 25153581475807469712135476776559283080497468613537
Fri Jun  8 01:29:39 2007  prp88 factor: 8819430499963616520071269821480424979203481406180373830145260754015654908007706407494709
Fri Jun  8 01:29:39 2007  elapsed time 07:10:58

[jasonp]

Originally Posted by fivemack

60hrs polynomial selection to get something with Murphy score 27.6e-12, 750 CPU-hours sieving (small primes up to 9e6, large primes up to 2^28) over a week or so on two dual-core machines to get 14.1 million unique relations. msieve-1.23 made a 1274168 x 1274368 matrix of weight 121993547, found 46 dependencies in 4.5 hours, and found the factorisation by the second square root at about 1 hour per square root.

Awesome.

Now if I can just get your C200 SNFS relations to produce nontrivial dependencies, I can put the postprocessing in maintenance mode and move to other things.