Running Msieve

[jasonp]

Originally Posted by frmky

Really??

There is a lot of pent-up demand, as before this there hasn't been any way to reliably complete these large factorizations. Now, with Franke's poly selection & lattice sieve from GGNFS and msieve's postprocessing, a complete, reliable, fast, open-source end-to-end tool is available.

Upon reflection, I think you're right that it would benefit the factoring community the most if I shelved temporarily my plans to improve poly selection and sieving, and instead concentrated on improving the postprocessing. Tom sent the logfile from his C200 job, and it looks like there are several places where it could have worked better. Not to mention that multithreaded linear algebra is really long overdue; the changes to make a cluster of machines do the linear algebra are very extensive, but just a few threads on a single machine doesn't look that difficult.

Tom, could you save the relations from this job and volunteer to test future msieve versions on them, or alternately put them somewhere I can download them?

Sander, good to hear things worked out. Did the square root complain at all? There are some changes in 1.20 that your job should have tested.

Thanks to everybody for your patience, these first few jobs are going to be kind of hazardous. I'll try to incorporate any suggestions into the next version of the library, so far you've only asked for easy stuff :)

jasonp

[smh]

Originally Posted by jasonp

Sander, good to hear things worked out. Did the square root complain at all? There are some changes in 1.20 that your job should have tested.

Not that i can see.

Fri May 04 09:57:04 2007  Msieve v. 1.20
Fri May 04 09:57:04 2007  random seeds: 16a82260 d5059ef4
Fri May 04 09:57:04 2007  factoring 4847897650674271589692214953548261100661467568048097743586796577329310971847070154311989950539483602079419687 (109 digits)
Fri May 04 09:57:05 2007  commencing number field sieve (109-digit input)
Fri May 04 09:57:05 2007  R0:  61705153508638067785728
Fri May 04 09:57:05 2007  R1: -1
Fri May 04 09:57:05 2007  A0:  21
Fri May 04 09:57:05 2007  A1:  0
Fri May 04 09:57:05 2007  A2:  0
Fri May 04 09:57:05 2007  A3:  0
Fri May 04 09:57:05 2007  A4:  0
Fri May 04 09:57:05 2007  A5:  8
Fri May 04 09:57:05 2007  size score = 5.767537e-008, Murphy alpha = 0.894296, combined = 4.280828e-008
Fri May 04 09:57:10 2007  restarting with 1995450 relations
Fri May 04 09:57:10 2007  generating factor base
Fri May 04 09:57:11 2007  factor base complete:
Fri May 04 09:57:11 2007  49098 rational roots (max prime = 599999)
Fri May 04 09:57:11 2007  64388 algebraic roots (max prime = 799999)
Fri May 04 09:57:11 2007  added 3280 free relations
Fri May 04 09:57:11 2007  
Fri May 04 09:57:11 2007  commencing relation filtering
Fri May 04 09:57:11 2007  commencing duplicate removal, pass 1
Fri May 04 09:57:26 2007  found 60319 hash collisions in 1998730 relations
Fri May 04 09:57:26 2007  commencing duplicate removal, pass 2
Fri May 04 09:57:30 2007  found 53306 duplicates and 1945424 unique relations
Fri May 04 09:57:30 2007  memory use: 36.9 MB
Fri May 04 09:57:31 2007  ignoring smallest 96761 rational and 97228 algebraic ideals
Fri May 04 09:57:31 2007  filtering rational ideals above 1254296
Fri May 04 09:57:31 2007  filtering algebraic ideals above 1254296
Fri May 04 09:57:31 2007  need 426775 more relations than ideals
Fri May 04 09:57:31 2007  commencing singleton removal, pass 1
Fri May 04 09:57:47 2007  relations with 0 large ideals: 77007
Fri May 04 09:57:47 2007  relations with 1 large ideals: 441070
Fri May 04 09:57:47 2007  relations with 2 large ideals: 826096
Fri May 04 09:57:47 2007  relations with 3 large ideals: 509663
Fri May 04 09:57:47 2007  relations with 4 large ideals: 91588
Fri May 04 09:57:47 2007  relations with 5 large ideals: 0
Fri May 04 09:57:47 2007  relations with 6 large ideals: 0
Fri May 04 09:57:47 2007  relations with 7+ large ideals: 0
Fri May 04 09:57:47 2007  1945424 relations and about 1857835 large ideals
Fri May 04 09:57:47 2007  commencing singleton removal, pass 2
Fri May 04 09:58:03 2007  found 956289 singletons
Fri May 04 09:58:03 2007  current dataset: 989135 relations and about 723354 large ideals
Fri May 04 09:58:03 2007  commencing singleton removal, pass 3
Fri May 04 09:58:12 2007  found 172795 singletons
Fri May 04 09:58:12 2007  current dataset: 816340 relations and about 539140 large ideals
Fri May 04 09:58:12 2007  commencing singleton removal, pass 4
Fri May 04 09:58:20 2007  found 46346 singletons
Fri May 04 09:58:20 2007  current dataset: 769994 relations and about 491813 large ideals
Fri May 04 09:58:20 2007  commencing singleton removal, final pass
Fri May 04 09:58:27 2007  memory use: 30.0 MB
Fri May 04 09:58:28 2007  commencing in-memory singleton removal
Fri May 04 09:58:28 2007  begin with 769994 relations and 505893 unique ideals
Fri May 04 09:58:28 2007  reduce to 715380 relations and 450609 ideals in 11 passes
Fri May 04 09:58:28 2007  max relations containing the same ideal: 18
Fri May 04 09:58:28 2007  not enough excess, attempting to create matrix anyway
Fri May 04 09:58:28 2007  ignoring smallest 96761 rational and 97228 algebraic ideals
Fri May 04 09:58:28 2007  filtering rational ideals above 1254296
Fri May 04 09:58:28 2007  filtering algebraic ideals above 1254296
Fri May 04 09:58:28 2007  need 223087 more relations than ideals
Fri May 04 09:58:28 2007  commencing singleton removal, final pass
Fri May 04 09:58:35 2007  memory use: 30.0 MB
Fri May 04 09:58:35 2007  commencing in-memory singleton removal
Fri May 04 09:58:35 2007  begin with 769994 relations and 505893 unique ideals
Fri May 04 09:58:36 2007  reduce to 715380 relations and 450609 ideals in 11 passes
Fri May 04 09:58:36 2007  max relations containing the same ideal: 18
Fri May 04 09:58:36 2007  removing 122181 relations and 101339 ideals in 20842 cliques
Fri May 04 09:58:36 2007  commencing in-memory singleton removal
Fri May 04 09:58:36 2007  begin with 593199 relations and 450609 unique ideals
Fri May 04 09:58:36 2007  reduce to 583463 relations and 339208 ideals in 7 passes
Fri May 04 09:58:36 2007  max relations containing the same ideal: 15
Fri May 04 09:58:36 2007  removing 89091 relations and 68249 ideals in 20842 cliques
Fri May 04 09:58:36 2007  commencing in-memory singleton removal
Fri May 04 09:58:36 2007  begin with 494372 relations and 339208 unique ideals
Fri May 04 09:58:36 2007  reduce to 487999 relations and 264374 ideals in 5 passes
Fri May 04 09:58:36 2007  max relations containing the same ideal: 11
Fri May 04 09:58:36 2007  removing 3672 relations and 3135 ideals in 537 cliques
Fri May 04 09:58:36 2007  commencing in-memory singleton removal
Fri May 04 09:58:36 2007  begin with 484327 relations and 264374 unique ideals
Fri May 04 09:58:36 2007  reduce to 484313 relations and 261225 ideals in 4 passes
Fri May 04 09:58:36 2007  max relations containing the same ideal: 11
Fri May 04 09:58:37 2007  relations with 0 large ideals: 77007
Fri May 04 09:58:37 2007  relations with 1 large ideals: 195878
Fri May 04 09:58:37 2007  relations with 2 large ideals: 159701
Fri May 04 09:58:37 2007  relations with 3 large ideals: 47226
Fri May 04 09:58:37 2007  relations with 4 large ideals: 4501
Fri May 04 09:58:37 2007  relations with 5 large ideals: 0
Fri May 04 09:58:37 2007  relations with 6 large ideals: 0
Fri May 04 09:58:37 2007  relations with 7+ large ideals: 0
Fri May 04 09:58:37 2007  commencing 2-way merge
Fri May 04 09:58:37 2007  merged 162162 relations
Fri May 04 09:58:37 2007  reduce to 322151 relation sets and 99063 unique ideals
Fri May 04 09:58:37 2007  commencing full merge
Fri May 04 09:58:37 2007  found 223088 cycles, need 194069
Fri May 04 09:58:38 2007  weight of 194069 cycles is about 4953602 (25.52/cycle)
Fri May 04 09:58:38 2007  distribution of cycle lengths:
Fri May 04 09:58:38 2007  1 relations: 77007
Fri May 04 09:58:38 2007  2 relations: 40826
Fri May 04 09:58:38 2007  3 relations: 29010
Fri May 04 09:58:38 2007  4 relations: 21539
Fri May 04 09:58:38 2007  5 relations: 15888
Fri May 04 09:58:38 2007  6 relations: 9355
Fri May 04 09:58:38 2007  7 relations: 444
Fri May 04 09:58:38 2007  8 relations: 0
Fri May 04 09:58:38 2007  9 relations: 0
Fri May 04 09:58:38 2007  10+ relations: 0
Fri May 04 09:58:38 2007  heaviest cycle: 7 relations
Fri May 04 09:58:38 2007  commencing cycle optimization
Fri May 04 09:58:38 2007  start with 470523 relations
Fri May 04 09:58:38 2007  pruned 2550 relations
Fri May 04 09:58:38 2007  distribution of cycle lengths:
Fri May 04 09:58:38 2007  1 relations: 77007
Fri May 04 09:58:38 2007  2 relations: 41045
Fri May 04 09:58:38 2007  3 relations: 29423
Fri May 04 09:58:38 2007  4 relations: 21730
Fri May 04 09:58:38 2007  5 relations: 15885
Fri May 04 09:58:38 2007  6 relations: 8591
Fri May 04 09:58:38 2007  7 relations: 388
Fri May 04 09:58:38 2007  8 relations: 0
Fri May 04 09:58:38 2007  9 relations: 0
Fri May 04 09:58:38 2007  10+ relations: 0
Fri May 04 09:58:38 2007  heaviest cycle: 7 relations
Fri May 04 09:58:38 2007  
Fri May 04 09:58:38 2007  commencing linear algebra
Fri May 04 09:58:38 2007  factor base loaded:
Fri May 04 09:58:38 2007  49098 rational ideals (max prime = 599999)
Fri May 04 09:58:38 2007  64388 algebraic ideals (max prime = 799999)
Fri May 04 09:58:38 2007  read 194069 cycles
Fri May 04 09:58:38 2007  cycles contain 379458 unique relations
Fri May 04 09:58:43 2007  read 379458 relations
Fri May 04 09:58:43 2007  using 32 quadratic characters above 33548840
Fri May 04 09:58:50 2007  matrix is 189193 x 194069 with weight 9370039 (avg 48.28/col)
Fri May 04 09:58:51 2007  filtering completed in 4 passes
Fri May 04 09:58:51 2007  matrix is 172108 x 172188 with weight 8052576 (avg 46.77/col)
Fri May 04 09:58:51 2007  saving the first 48 matrix rows for later
Fri May 04 09:58:51 2007  matrix is 172060 x 172188 with weight 4490170 (avg 26.08/col)
Fri May 04 09:58:51 2007  matrix includes 64 packed rows
Fri May 04 09:58:51 2007  using block size 65536 for processor cache size 4096 kB
Fri May 04 10:00:57 2007  lanczos halted after 2721 iterations
Fri May 04 10:00:57 2007  recovered 5 nontrivial dependencies
Fri May 04 10:00:57 2007  
Fri May 04 10:00:57 2007  commencing square root phase
Fri May 04 10:00:57 2007  reading relations for dependency 1
Fri May 04 10:00:57 2007  read 86209 cycles
Fri May 04 10:00:58 2007  cycles contain 175915 unique relations
Fri May 04 10:01:01 2007  read 175915 relations
Fri May 04 10:01:01 2007  multiplying 195548 relations
Fri May 04 10:01:17 2007  multiply complete, coefficients have about 4.34 million bits
Fri May 04 10:01:17 2007  initial square root is modulo 98911
Fri May 04 10:01:41 2007  reading relations for dependency 2
Fri May 04 10:01:42 2007  read 85883 cycles
Fri May 04 10:01:42 2007  cycles contain 174868 unique relations
Fri May 04 10:01:45 2007  read 174868 relations
Fri May 04 10:01:46 2007  multiplying 194362 relations
Fri May 04 10:02:02 2007  multiply complete, coefficients have about 4.31 million bits
Fri May 04 10:02:02 2007  initial square root is modulo 92221
Fri May 04 10:02:25 2007  prp49 factor: 5993099232275355068436021236102118487020377470829
Fri May 04 10:02:25 2007  prp60 factor: 808913295572732678194869854770165327780010017406887014536803
Fri May 04 10:02:25 2007  elapsed time 00:05:21

[fivemack]

Thu May  3 20:53:39 2007  saving the first 48 matrix rows for later
Thu May  3 20:53:43 2007  matrix is 4669796 x 4669924 with weight 181181856 (avg 38.80/col)
Thu May  3 20:53:44 2007  matrix includes 64 packed rows
Thu May  3 20:53:44 2007  using block size 65536 for processor cache size 4096 kB
Sun May  6 10:32:43 2007  lanczos halted after 73808 iterations
Sun May  6 10:34:56 2007  lanczos error: only trivial dependencies found

I've been continuing sieving on the other CPU the while, so might as well add those relations and try again. I'm never quite sure whether 'only trivial dependencies found' is an accident or a sign of a problem in the filtering; to have made 16 unlucky choices (I presume it's 16, block=64 and 48 matrix rows saved for later) suggests that unlucky choices are rather common.

[jasonp]

Originally Posted by fivemack

I've been continuing sieving on the other CPU the while, so might as well add those relations and try again. I'm never quite sure whether 'only trivial dependencies found' is an accident or a sign of a problem in the filtering; to have made 16 unlucky choices (I presume it's 16, block=64 and 48 matrix rows saved for later) suggests that unlucky choices are rather common.

Rats. It's interesting that Sander's factorization only came up with 5 dependencies and yours came up with zero; I've never seen the NFS linear algebra come up with less than ~40 dependencies before now. You may want to try is changing the value of QCB_SIZE at the top of gnfs/gf2.c from 32 to 48 or maybe even 60, and also changing NUM_EXTRA_RELATIONS in gnfs/gnfs.h from 80 to maybe 200. If you're concerned that 48 out of 64 dependencies get sacrificed try reducing POST_LANCZOS_ROWS in common/lanczos/lanczos.c

Sander, your job only takes a few minutes; does rerunning the postprocessing consistently give you so few dependencies?

I have several changes in the pipeline that will make filtering behave a little better for big jobs like yours, hopefully they'll be ready by the end of the week.

[smh]

Originally Posted by jasonp

Sander, your job only takes a few minutes; does rerunning the postprocessing consistently give you so few dependencies?

Sorry, don't have the relations any more.

I'm doing another SNFS with GGNFS at the moment (dif ~127, deg. 4) for which I'm saving relations. I'll try finishing that one with msieve and pay attention to the number of dependencies found.

Do you want me to try the same number again? Sieving only takes an hour or so.

[fivemack]

Here's the log after re-running with all the modifications you suggested and a couple million more relations. I'll presumably know by Wednesday whether the modifications helped.

[jasonp]

Originally Posted by smh

Do you want me to try the same number again? Sieving only takes an hour or so.

That would be helpful, thanks.

[frmky]

Hi,

The C211-difficulty SNFS finished successfully on the third dependency. The log is below. Jason: I sent you a PM with the address where you can download the relations. Let me know if you got them ok.

Greg

Fri May  4 23:56:15 2007  
Fri May  4 23:56:15 2007  
Fri May  4 23:56:15 2007  Msieve v. 1.20
Fri May  4 23:56:15 2007  random seeds: a0754173 6494bc15
Fri May  4 23:56:15 2007  factoring 1239933213047612666105646898805318952130080877894133506922312417689891534360814588585024998064920593215273393369005017406401346359167831352246502119380880242260898574629156714950720293624755668391314983709 (205 digits)
Fri May  4 23:56:15 2007  commencing number field sieve (204-digit input)
Fri May  4 23:56:16 2007  R0: -497745340030349688137123548984527587890625
Fri May  4 23:56:16 2007  R1:  688579136852433871931703296
Fri May  4 23:56:16 2007  A0:  1
Fri May  4 23:56:16 2007  A1:  0
Fri May  4 23:56:16 2007  A2:  0
Fri May  4 23:56:16 2007  A3:  0
Fri May  4 23:56:16 2007  A4:  0
Fri May  4 23:56:16 2007  A5:  65
Fri May  4 23:56:16 2007  size score = 2.838529e-14, Murphy alpha = -0.359436, combined = 3.199831e-14
Fri May  4 23:59:23 2007  restarting with 54512558 relations
Fri May  4 23:59:23 2007  generating factor base
Fri May  4 23:59:37 2007  factor base complete:
Fri May  4 23:59:37 2007  788060 rational roots (max prime = 11999989)
Fri May  4 23:59:37 2007  1150546 algebraic roots (max prime = 17999987)
Fri May  4 23:59:38 2007  added 57389 free relations
Fri May  4 23:59:38 2007  
Fri May  4 23:59:38 2007  commencing relation filtering
Fri May  4 23:59:38 2007  commencing duplicate removal, pass 1
Sat May  5 00:00:08 2007  error -1 reading relation 2374496
Sat May  5 00:00:29 2007  error -1 reading relation 4350677
Sat May  5 00:00:30 2007  error -1 reading relation 4450658
Sat May  5 00:00:32 2007  error -1 reading relation 4594950
Sat May  5 00:00:34 2007  error -1 reading relation 4886581
Sat May  5 00:00:41 2007  error -5 reading relation 5520276
Sat May  5 00:01:05 2007  error -10 reading relation 7851632
Sat May  5 00:01:28 2007  error -1 reading relation 10050189
Sat May  5 00:01:51 2007  error -1 reading relation 12243226
Sat May  5 00:01:54 2007  error -1 reading relation 12570491
Sat May  5 00:01:58 2007  error -1 reading relation 12941663
Sat May  5 00:02:00 2007  error -1 reading relation 13152492
Sat May  5 00:02:02 2007  error -10 reading relation 13318212
Sat May  5 00:02:02 2007  error -1 reading relation 13318213
Sat May  5 00:02:11 2007  error -1 reading relation 14156154
Sat May  5 00:02:12 2007  error -1 reading relation 14232628
Sat May  5 00:02:24 2007  error -1 reading relation 15395154
Sat May  5 00:02:24 2007  error -1 reading relation 15395157
Sat May  5 00:02:27 2007  error -10 reading relation 15675051
Sat May  5 00:02:41 2007  error -10 reading relation 16998567
Sat May  5 00:02:41 2007  error -10 reading relation 16998568
Sat May  5 00:03:24 2007  error -1 reading relation 21076829
Sat May  5 00:03:33 2007  error -1 reading relation 21901154
Sat May  5 00:04:08 2007  error -10 reading relation 25176563
Sat May  5 00:04:17 2007  error -14 reading relation 26050560
Sat May  5 00:04:26 2007  error -1 reading relation 27030100
Sat May  5 00:05:15 2007  error -1 reading relation 32006666
Sat May  5 00:06:02 2007  error -1 reading relation 36817312
Sat May  5 00:06:08 2007  error -1 reading relation 37407300
Sat May  5 00:06:37 2007  error -1 reading relation 40354777
Sat May  5 00:06:46 2007  error -5 reading relation 41133658
Sat May  5 00:06:47 2007  error -1 reading relation 41192816
Sat May  5 00:07:24 2007  error -1 reading relation 44813497
Sat May  5 00:07:46 2007  error -1 reading relation 46975368
Sat May  5 00:08:05 2007  error -1 reading relation 48828553
Sat May  5 00:08:10 2007  error -1 reading relation 49329612
Sat May  5 00:08:33 2007  error -1 reading relation 51623135
Sat May  5 00:08:35 2007  error -1 reading relation 51775788
Sat May  5 00:08:37 2007  error -1 reading relation 51938279
Sat May  5 00:08:38 2007  error -1 reading relation 52080156
Sat May  5 00:08:38 2007  error -10 reading relation 52080158
Sat May  5 00:08:50 2007  error -1 reading relation 53214099
Sat May  5 00:08:53 2007  error -5 reading relation 53535341
Sat May  5 00:08:53 2007  error -1 reading relation 53535342
Sat May  5 00:09:00 2007  error -10 reading relation 54279199
Sat May  5 00:09:00 2007  error -1 reading relation 54279201
Sat May  5 00:09:05 2007  found 10452495 hash collisions in 54569901 relations
Sat May  5 00:09:05 2007  commencing duplicate removal, pass 2
Sat May  5 00:13:27 2007  found 6372228 duplicates and 48197673 unique relations
Sat May  5 00:13:27 2007  memory use: 270.4 MB
Sat May  5 00:13:43 2007  ignoring smallest 1534396 rational and 1533107 algebraic ideals
Sat May  5 00:13:43 2007  filtering rational ideals above 24463115
Sat May  5 00:13:43 2007  filtering algebraic ideals above 24463115
Sat May  5 00:13:43 2007  need 6748506 more relations than ideals
Sat May  5 00:13:43 2007  commencing singleton removal, pass 1
Sat May  5 00:33:11 2007  relations with 0 large ideals: 623590
Sat May  5 00:33:11 2007  relations with 1 large ideals: 4004760
Sat May  5 00:33:11 2007  relations with 2 large ideals: 11526320
Sat May  5 00:33:11 2007  relations with 3 large ideals: 16689901
Sat May  5 00:33:11 2007  relations with 4 large ideals: 12014306
Sat May  5 00:33:11 2007  relations with 5 large ideals: 3338796
Sat May  5 00:33:11 2007  relations with 6 large ideals: 0
Sat May  5 00:33:11 2007  relations with 7+ large ideals: 0
Sat May  5 00:33:11 2007  48197673 relations and about 30988063 large ideals
Sat May  5 00:33:11 2007  commencing singleton removal, pass 2
Sat May  5 00:45:59 2007  found 7900660 singletons
Sat May  5 00:45:59 2007  current dataset: 40297013 relations and about 22587432 large ideals
Sat May  5 00:45:59 2007  commencing singleton removal, pass 3
Sat May  5 00:57:33 2007  found 948173 singletons
Sat May  5 00:57:33 2007  current dataset: 39348840 relations and about 21629967 large ideals
Sat May  5 00:57:35 2007  commencing singleton removal, pass 4
Sat May  5 01:13:21 2007  found 101559 singletons
Sat May  5 01:13:21 2007  current dataset: 39247281 relations and about 21528289 large ideals
Sat May  5 01:13:22 2007  commencing singleton removal, pass 5
Sat May  5 01:21:40 2007  found 9655 singletons
Sat May  5 01:21:40 2007  current dataset: 39237626 relations and about 21518632 large ideals
Sat May  5 01:21:40 2007  commencing singleton removal, final pass
Sat May  5 01:31:18 2007  memory use: 1306.5 MB
Sat May  5 01:31:18 2007  commencing in-memory singleton removal
Sat May  5 01:31:23 2007  begin with 39237626 relations and 31087579 unique ideals
Sat May  5 01:32:28 2007  reduce to 29178615 relations and 20405697 ideals in 14 passes
Sat May  5 01:32:28 2007  max relations containing the same ideal: 57
Sat May  5 01:32:49 2007  removing 859875 relations and 759875 ideals in 100000 cliques
Sat May  5 01:32:50 2007  commencing in-memory singleton removal
Sat May  5 01:32:54 2007  begin with 28318740 relations and 20405697 unique ideals
Sat May  5 01:33:23 2007  reduce to 28306482 relations and 19633529 ideals in 7 passes
Sat May  5 01:33:23 2007  max relations containing the same ideal: 56
Sat May  5 01:33:42 2007  removing 646247 relations and 546247 ideals in 100000 cliques
Sat May  5 01:33:43 2007  commencing in-memory singleton removal
Sat May  5 01:33:46 2007  begin with 27660235 relations and 19633529 unique ideals
Sat May  5 01:34:10 2007  reduce to 27652647 relations and 19079670 ideals in 6 passes
Sat May  5 01:34:10 2007  max relations containing the same ideal: 56
Sat May  5 01:34:29 2007  removing 576456 relations and 476456 ideals in 100000 cliques
Sat May  5 01:34:30 2007  commencing in-memory singleton removal
Sat May  5 01:34:33 2007  begin with 27076191 relations and 19079670 unique ideals
Sat May  5 01:34:53 2007  reduce to 27070079 relations and 18597078 ideals in 5 passes
Sat May  5 01:34:53 2007  max relations containing the same ideal: 56
Sat May  5 01:35:11 2007  removing 534474 relations and 434474 ideals in 100000 cliques
Sat May  5 01:35:12 2007  commencing in-memory singleton removal
Sat May  5 01:35:15 2007  begin with 26535605 relations and 18597078 unique ideals
Sat May  5 01:35:38 2007  reduce to 26529636 relations and 18156618 ideals in 6 passes
Sat May  5 01:35:38 2007  max relations containing the same ideal: 53
Sat May  5 01:35:55 2007  removing 506209 relations and 406209 ideals in 100000 cliques
Sat May  5 01:35:56 2007  commencing in-memory singleton removal
Sat May  5 01:35:59 2007  begin with 26023427 relations and 18156618 unique ideals
Sat May  5 01:36:18 2007  reduce to 26017970 relations and 17744930 ideals in 5 passes
Sat May  5 01:36:18 2007  max relations containing the same ideal: 52
Sat May  5 01:36:35 2007  removing 484774 relations and 384774 ideals in 100000 cliques
Sat May  5 01:36:36 2007  commencing in-memory singleton removal
Sat May  5 01:36:39 2007  begin with 25533196 relations and 17744930 unique ideals
Sat May  5 01:37:01 2007  reduce to 25528161 relations and 17355102 ideals in 6 passes
Sat May  5 01:37:01 2007  max relations containing the same ideal: 51
Sat May  5 01:37:18 2007  removing 467273 relations and 367273 ideals in 100000 cliques
Sat May  5 01:37:18 2007  commencing in-memory singleton removal
Sat May  5 01:37:21 2007  begin with 25060888 relations and 17355102 unique ideals
Sat May  5 01:37:39 2007  reduce to 25056107 relations and 16983030 ideals in 5 passes
Sat May  5 01:37:39 2007  max relations containing the same ideal: 51
Sat May  5 01:37:55 2007  removing 450718 relations and 350718 ideals in 100000 cliques
Sat May  5 01:37:56 2007  commencing in-memory singleton removal
Sat May  5 01:37:59 2007  begin with 24605389 relations and 16983030 unique ideals
Sat May  5 01:38:17 2007  reduce to 24600542 relations and 16627449 ideals in 5 passes
Sat May  5 01:38:17 2007  max relations containing the same ideal: 50
Sat May  5 01:38:33 2007  removing 441666 relations and 341666 ideals in 100000 cliques
Sat May  5 01:38:33 2007  commencing in-memory singleton removal
Sat May  5 01:38:36 2007  begin with 24158876 relations and 16627449 unique ideals
Sat May  5 01:38:53 2007  reduce to 24154652 relations and 16281549 ideals in 5 passes
Sat May  5 01:38:53 2007  max relations containing the same ideal: 50
Sat May  5 01:39:09 2007  removing 427538 relations and 327538 ideals in 100000 cliques
Sat May  5 01:39:10 2007  commencing in-memory singleton removal
Sat May  5 01:39:12 2007  begin with 23727114 relations and 16281549 unique ideals
Sat May  5 01:39:29 2007  reduce to 23722452 relations and 15949330 ideals in 5 passes
Sat May  5 01:39:29 2007  max relations containing the same ideal: 49
Sat May  5 01:39:44 2007  removing 423387 relations and 323387 ideals in 100000 cliques
Sat May  5 01:39:45 2007  commencing in-memory singleton removal
Sat May  5 01:39:48 2007  begin with 23299065 relations and 15949330 unique ideals
Sat May  5 01:40:04 2007  reduce to 23294811 relations and 15621674 ideals in 5 passes
Sat May  5 01:40:04 2007  max relations containing the same ideal: 49
Sat May  5 01:40:19 2007  removing 413676 relations and 313676 ideals in 100000 cliques
Sat May  5 01:40:20 2007  commencing in-memory singleton removal
Sat May  5 01:40:23 2007  begin with 22881135 relations and 15621674 unique ideals
Sat May  5 01:40:35 2007  reduce to 22876741 relations and 15303588 ideals in 4 passes
Sat May  5 01:40:35 2007  max relations containing the same ideal: 49
Sat May  5 01:40:50 2007  removing 407271 relations and 307271 ideals in 100000 cliques
Sat May  5 01:40:51 2007  commencing in-memory singleton removal
Sat May  5 01:40:53 2007  begin with 22469470 relations and 15303588 unique ideals
Sat May  5 01:41:09 2007  reduce to 22465356 relations and 14992191 ideals in 5 passes
Sat May  5 01:41:09 2007  max relations containing the same ideal: 49
Sat May  5 01:41:23 2007  removing 399730 relations and 299730 ideals in 100000 cliques
Sat May  5 01:41:24 2007  commencing in-memory singleton removal
Sat May  5 01:41:26 2007  begin with 22065626 relations and 14992191 unique ideals
Sat May  5 01:41:41 2007  reduce to 22061643 relations and 14688466 ideals in 5 passes
Sat May  5 01:41:41 2007  max relations containing the same ideal: 49
Sat May  5 01:41:55 2007  removing 393447 relations and 293447 ideals in 100000 cliques
Sat May  5 01:41:56 2007  commencing in-memory singleton removal
Sat May  5 01:41:59 2007  begin with 21668196 relations and 14688466 unique ideals
Sat May  5 01:42:13 2007  reduce to 21663884 relations and 14390692 ideals in 5 passes
Sat May  5 01:42:13 2007  max relations containing the same ideal: 48
Sat May  5 01:42:27 2007  removing 390411 relations and 290411 ideals in 100000 cliques
Sat May  5 01:42:28 2007  commencing in-memory singleton removal
Sat May  5 01:42:30 2007  begin with 21273473 relations and 14390692 unique ideals
Sat May  5 01:42:45 2007  reduce to 21269325 relations and 14096119 ideals in 5 passes
Sat May  5 01:42:45 2007  max relations containing the same ideal: 48
Sat May  5 01:42:58 2007  removing 383928 relations and 283928 ideals in 100000 cliques
Sat May  5 01:42:59 2007  commencing in-memory singleton removal
Sat May  5 01:43:01 2007  begin with 20885397 relations and 14096119 unique ideals
Sat May  5 01:43:15 2007  reduce to 20881220 relations and 13807991 ideals in 5 passes
Sat May  5 01:43:15 2007  max relations containing the same ideal: 47
Sat May  5 01:43:29 2007  removing 382680 relations and 282680 ideals in 100000 cliques
Sat May  5 01:43:29 2007  commencing in-memory singleton removal
Sat May  5 01:43:32 2007  begin with 20498540 relations and 13807991 unique ideals
Sat May  5 01:43:45 2007  reduce to 20494457 relations and 13521216 ideals in 5 passes
Sat May  5 01:43:45 2007  max relations containing the same ideal: 47
Sat May  5 01:43:58 2007  removing 374988 relations and 274988 ideals in 100000 cliques
Sat May  5 01:43:59 2007  commencing in-memory singleton removal
Sat May  5 01:44:01 2007  begin with 20119469 relations and 13521216 unique ideals
Sat May  5 01:44:12 2007  reduce to 20115043 relations and 13241781 ideals in 4 passes
Sat May  5 01:44:12 2007  max relations containing the same ideal: 47
Sat May  5 01:44:24 2007  removing 368871 relations and 268871 ideals in 100000 cliques
Sat May  5 01:44:25 2007  commencing in-memory singleton removal
Sat May  5 01:44:27 2007  begin with 19746172 relations and 13241781 unique ideals
Sat May  5 01:44:38 2007  reduce to 19741203 relations and 12967923 ideals in 4 passes
Sat May  5 01:44:38 2007  max relations containing the same ideal: 45
Sat May  5 01:44:50 2007  removing 373843 relations and 273843 ideals in 100000 cliques
Sat May  5 01:44:51 2007  commencing in-memory singleton removal
Sat May  5 01:44:53 2007  begin with 19367360 relations and 12967923 unique ideals
Sat May  5 01:45:09 2007  reduce to 19363381 relations and 12690071 ideals in 6 passes
Sat May  5 01:45:09 2007  max relations containing the same ideal: 44
Sat May  5 01:45:21 2007  removing 361174 relations and 261174 ideals in 100000 cliques
Sat May  5 01:45:22 2007  commencing in-memory singleton removal
Sat May  5 01:45:24 2007  begin with 19002207 relations and 12690071 unique ideals
Sat May  5 01:45:34 2007  reduce to 18998051 relations and 12424722 ideals in 4 passes
Sat May  5 01:45:34 2007  max relations containing the same ideal: 44
Sat May  5 01:45:45 2007  removing 362082 relations and 262082 ideals in 100000 cliques
Sat May  5 01:45:46 2007  commencing in-memory singleton removal
Sat May  5 01:45:48 2007  begin with 18635969 relations and 12424722 unique ideals
Sat May  5 01:46:00 2007  reduce to 18631574 relations and 12158222 ideals in 5 passes
Sat May  5 01:46:00 2007  max relations containing the same ideal: 44
Sat May  5 01:46:12 2007  removing 358173 relations and 258173 ideals in 100000 cliques
Sat May  5 01:46:13 2007  commencing in-memory singleton removal
Sat May  5 01:46:15 2007  begin with 18273401 relations and 12158222 unique ideals
Sat May  5 01:46:26 2007  reduce to 18269030 relations and 11895660 ideals in 5 passes
Sat May  5 01:46:26 2007  max relations containing the same ideal: 44
Sat May  5 01:46:38 2007  removing 354160 relations and 254160 ideals in 100000 cliques
Sat May  5 01:46:38 2007  commencing in-memory singleton removal
Sat May  5 01:46:40 2007  begin with 17914870 relations and 11895660 unique ideals
Sat May  5 01:46:52 2007  reduce to 17910141 relations and 11636744 ideals in 5 passes
Sat May  5 01:46:52 2007  max relations containing the same ideal: 44
Sat May  5 01:47:03 2007  removing 354710 relations and 254710 ideals in 100000 cliques
Sat May  5 01:47:04 2007  commencing in-memory singleton removal
Sat May  5 01:47:06 2007  begin with 17555431 relations and 11636744 unique ideals
Sat May  5 01:47:15 2007  reduce to 17550702 relations and 11377274 ideals in 4 passes
Sat May  5 01:47:15 2007  max relations containing the same ideal: 43
Sat May  5 01:47:25 2007  removing 354704 relations and 254704 ideals in 100000 cliques
Sat May  5 01:47:26 2007  commencing in-memory singleton removal
Sat May  5 01:47:28 2007  begin with 17195998 relations and 11377274 unique ideals
Sat May  5 01:47:37 2007  reduce to 17191524 relations and 11118065 ideals in 4 passes
Sat May  5 01:47:37 2007  max relations containing the same ideal: 43
Sat May  5 01:47:47 2007  removing 349672 relations and 249672 ideals in 100000 cliques
Sat May  5 01:47:48 2007  commencing in-memory singleton removal
Sat May  5 01:47:50 2007  begin with 16841852 relations and 11118065 unique ideals
Sat May  5 01:48:00 2007  reduce to 16837255 relations and 10863773 ideals in 5 passes
Sat May  5 01:48:00 2007  max relations containing the same ideal: 42
Sat May  5 01:48:11 2007  removing 347348 relations and 247348 ideals in 100000 cliques
Sat May  5 01:48:11 2007  commencing in-memory singleton removal
Sat May  5 01:48:13 2007  begin with 16489907 relations and 10863773 unique ideals
Sat May  5 01:48:24 2007  reduce to 16485197 relations and 10611685 ideals in 5 passes
Sat May  5 01:48:24 2007  max relations containing the same ideal: 42
Sat May  5 01:48:34 2007  removing 348022 relations and 248022 ideals in 100000 cliques
Sat May  5 01:48:34 2007  commencing in-memory singleton removal
Sat May  5 01:48:36 2007  begin with 16137175 relations and 10611685 unique ideals
Sat May  5 01:48:46 2007  reduce to 16132512 relations and 10358966 ideals in 5 passes
Sat May  5 01:48:46 2007  max relations containing the same ideal: 41
Sat May  5 01:48:56 2007  removing 344721 relations and 244721 ideals in 100000 cliques
Sat May  5 01:48:57 2007  commencing in-memory singleton removal
Sat May  5 01:48:58 2007  begin with 15787791 relations and 10358966 unique ideals
Sat May  5 01:49:06 2007  reduce to 15782955 relations and 10109370 ideals in 4 passes
Sat May  5 01:49:06 2007  max relations containing the same ideal: 40
Sat May  5 01:49:16 2007  removing 343483 relations and 243483 ideals in 100000 cliques
Sat May  5 01:49:16 2007  commencing in-memory singleton removal
Sat May  5 01:49:18 2007  begin with 15439472 relations and 10109370 unique ideals
Sat May  5 01:49:28 2007  reduce to 15434460 relations and 9860841 ideals in 5 passes
Sat May  5 01:49:28 2007  max relations containing the same ideal: 40
Sat May  5 01:49:37 2007  removing 341223 relations and 241223 ideals in 100000 cliques
Sat May  5 01:49:38 2007  commencing in-memory singleton removal
Sat May  5 01:49:39 2007  begin with 15093237 relations and 9860841 unique ideals
Sat May  5 01:49:47 2007  reduce to 15087837 relations and 9614171 ideals in 4 passes
Sat May  5 01:49:47 2007  max relations containing the same ideal: 38
Sat May  5 01:49:56 2007  removing 339649 relations and 239649 ideals in 100000 cliques
Sat May  5 01:49:56 2007  commencing in-memory singleton removal
Sat May  5 01:49:58 2007  begin with 14748188 relations and 9614171 unique ideals
Sat May  5 01:50:07 2007  reduce to 14742694 relations and 9368968 ideals in 5 passes
Sat May  5 01:50:07 2007  max relations containing the same ideal: 37
Sat May  5 01:50:16 2007  removing 338290 relations and 238290 ideals in 100000 cliques
Sat May  5 01:50:17 2007  commencing in-memory singleton removal
Sat May  5 01:50:18 2007  begin with 14404404 relations and 9368968 unique ideals
Sat May  5 01:50:27 2007  reduce to 14398498 relations and 9124715 ideals in 5 passes
Sat May  5 01:50:27 2007  max relations containing the same ideal: 36
Sat May  5 01:50:36 2007  removing 216605 relations and 157578 ideals in 59027 cliques
Sat May  5 01:50:36 2007  commencing in-memory singleton removal
Sat May  5 01:50:38 2007  begin with 14181893 relations and 9124715 unique ideals
Sat May  5 01:50:46 2007  reduce to 14179899 relations and 8965129 ideals in 5 passes
Sat May  5 01:50:46 2007  max relations containing the same ideal: 36
Sat May  5 01:50:49 2007  ignoring smallest 802240 rational and 801711 algebraic ideals
Sat May  5 01:50:49 2007  filtering rational ideals above 12231557
Sat May  5 01:50:49 2007  filtering algebraic ideals above 12231557
Sat May  5 01:50:49 2007  need 3312903 more relations than ideals
Sat May  5 01:50:49 2007  commencing singleton removal, final pass
Sat May  5 01:56:13 2007  memory use: 544.8 MB
Sat May  5 01:56:13 2007  commencing in-memory singleton removal
Sat May  5 01:56:14 2007  begin with 14179899 relations and 10426940 unique ideals
Sat May  5 01:56:25 2007  reduce to 14164461 relations and 10411497 ideals in 5 passes
Sat May  5 01:56:25 2007  max relations containing the same ideal: 44
Sat May  5 01:56:35 2007  removing 336731 relations and 236731 ideals in 100000 cliques
Sat May  5 01:56:36 2007  commencing in-memory singleton removal
Sat May  5 01:56:37 2007  begin with 13827730 relations and 10411497 unique ideals
Sat May  5 01:56:48 2007  reduce to 13820755 relations and 10167709 ideals in 5 passes
Sat May  5 01:56:48 2007  max relations containing the same ideal: 43
Sat May  5 01:56:57 2007  removing 336769 relations and 236769 ideals in 100000 cliques
Sat May  5 01:56:58 2007  commencing in-memory singleton removal
Sat May  5 01:57:00 2007  begin with 13483986 relations and 10167709 unique ideals
Sat May  5 01:57:10 2007  reduce to 13477748 relations and 9924648 ideals in 5 passes
Sat May  5 01:57:10 2007  max relations containing the same ideal: 42
Sat May  5 01:57:19 2007  removing 335830 relations and 235830 ideals in 100000 cliques
Sat May  5 01:57:20 2007  commencing in-memory singleton removal
Sat May  5 01:57:22 2007  begin with 13141918 relations and 9924648 unique ideals
Sat May  5 01:57:30 2007  reduce to 13135459 relations and 9682294 ideals in 4 passes
Sat May  5 01:57:30 2007  max relations containing the same ideal: 41
Sat May  5 01:57:39 2007  removing 337042 relations and 237042 ideals in 100000 cliques
Sat May  5 01:57:39 2007  commencing in-memory singleton removal
Sat May  5 01:57:41 2007  begin with 12798417 relations and 9682294 unique ideals
Sat May  5 01:57:50 2007  reduce to 12792569 relations and 9439331 ideals in 5 passes
Sat May  5 01:57:50 2007  max relations containing the same ideal: 41
Sat May  5 01:57:59 2007  removing 156559 relations and 116225 ideals in 40334 cliques
Sat May  5 01:58:00 2007  commencing in-memory singleton removal
Sat May  5 01:58:01 2007  begin with 12636010 relations and 9439331 unique ideals
Sat May  5 01:58:09 2007  reduce to 12635085 relations and 9322178 ideals in 4 passes
Sat May  5 01:58:09 2007  max relations containing the same ideal: 41
Sat May  5 01:58:14 2007  relations with 0 large ideals: 44694
Sat May  5 01:58:14 2007  relations with 1 large ideals: 343315
Sat May  5 01:58:14 2007  relations with 2 large ideals: 1881643
Sat May  5 01:58:14 2007  relations with 3 large ideals: 4101856
Sat May  5 01:58:14 2007  relations with 4 large ideals: 4150083
Sat May  5 01:58:14 2007  relations with 5 large ideals: 1861930
Sat May  5 01:58:14 2007  relations with 6 large ideals: 242787
Sat May  5 01:58:14 2007  relations with 7+ large ideals: 8777
Sat May  5 01:58:14 2007  commencing 2-way merge
Sat May  5 01:58:26 2007  merged 3584927 relations
Sat May  5 01:58:30 2007  reduce to 9050158 relation sets and 5737251 unique ideals
Sat May  5 01:58:30 2007  commencing full merge
Sat May  5 02:23:27 2007  found 4356272 cycles, need 2742331
Sat May  5 02:23:30 2007  weight of 2742331 cycles is about 185944504 (67.81/cycle)
Sat May  5 02:23:30 2007  distribution of cycle lengths:
Sat May  5 02:23:30 2007  1 relations: 263644
Sat May  5 02:23:30 2007  2 relations: 294809
Sat May  5 02:23:30 2007  3 relations: 326793
Sat May  5 02:23:30 2007  4 relations: 337506
Sat May  5 02:23:30 2007  5 relations: 343608
Sat May  5 02:23:30 2007  6 relations: 333887
Sat May  5 02:23:30 2007  7 relations: 319521
Sat May  5 02:23:30 2007  8 relations: 285438
Sat May  5 02:23:30 2007  9 relations: 212074
Sat May  5 02:23:30 2007  10+ relations: 25051
Sat May  5 02:23:30 2007  heaviest cycle: 11 relations
Sat May  5 02:23:30 2007  commencing cycle optimization
Sat May  5 02:39:03 2007  start with 13584567 relations
Sat May  5 02:40:46 2007  pruned 265073 relations
Sat May  5 02:40:48 2007  distribution of cycle lengths:
Sat May  5 02:40:48 2007  1 relations: 263644
Sat May  5 02:40:48 2007  2 relations: 300817
Sat May  5 02:40:48 2007  3 relations: 339738
Sat May  5 02:40:48 2007  4 relations: 347948
Sat May  5 02:40:49 2007  5 relations: 357809
Sat May  5 02:40:49 2007  6 relations: 345040
Sat May  5 02:40:49 2007  7 relations: 325194
Sat May  5 02:40:49 2007  8 relations: 270245
Sat May  5 02:40:50 2007  9 relations: 173479
Sat May  5 02:40:50 2007  10+ relations: 18417
Sat May  5 02:40:50 2007  heaviest cycle: 11 relations
Sat May  5 02:40:51 2007  c205 factor: 1239933213047612666105646898805318952130080877894133506922312417689891534360814588585024998064920593215273393369005017406401346359167831352246502119380880242260898574629156714950720293624755668391314983709
Sat May  5 02:40:53 2007  elapsed time 02:44:38
Sat May  5 15:53:44 2007  
Sat May  5 15:53:44 2007  
Sat May  5 15:53:44 2007  Msieve v. 1.20
Sat May  5 15:53:44 2007  random seeds: 3b843e63 8e05ef09
Sat May  5 15:53:44 2007  factoring 1239933213047612666105646898805318952130080877894133506922312417689891534360814588585024998064920593215273393369005017406401346359167831352246502119380880242260898574629156714950720293624755668391314983709 (205 digits)
Sat May  5 15:53:45 2007  commencing number field sieve (204-digit input)
Sat May  5 15:53:45 2007  R0: -497745340030349688137123548984527587890625
Sat May  5 15:53:45 2007  R1:  688579136852433871931703296
Sat May  5 15:53:45 2007  A0:  1
Sat May  5 15:53:45 2007  A1:  0
Sat May  5 15:53:45 2007  A2:  0
Sat May  5 15:53:45 2007  A3:  0
Sat May  5 15:53:45 2007  A4:  0
Sat May  5 15:53:45 2007  A5:  65
Sat May  5 15:53:45 2007  size score = 2.838529e-14, Murphy alpha = -0.313103, combined = 3.150791e-14
Sat May  5 15:53:45 2007  
Sat May  5 15:53:45 2007  commencing linear algebra
Sat May  5 15:53:47 2007  factor base loaded:
Sat May  5 15:53:47 2007  788060 rational ideals (max prime = 11999989)
Sat May  5 15:53:47 2007  1150546 algebraic ideals (max prime = 17999987)
Sat May  5 15:53:54 2007  read 2742331 cycles
Sat May  5 15:54:05 2007  cycles contain 7459668 unique relations
Sat May  5 15:57:38 2007  read 7459668 relations
Sat May  5 15:57:54 2007  using 32 quadratic characters above 536870718
Sat May  5 16:05:24 2007  matrix is 2736725 x 2742331 with weight 253920310 (avg 92.59/col)
Sat May  5 16:06:02 2007  filtering completed in 3 passes
Sat May  5 16:06:04 2007  matrix is 2723848 x 2723928 with weight 251437586 (avg 92.31/col)
Sat May  5 16:06:48 2007  saving the first 48 matrix rows for later
Sat May  5 16:06:52 2007  matrix is 2723800 x 2723928 with weight 191015090 (avg 70.12/col)
Sat May  5 16:06:52 2007  matrix includes 64 packed rows
Sat May  5 16:06:52 2007  using block size 43690 for processor cache size 1024 kB
Mon May  7 09:06:24 2007  lanczos halted after 43072 iterations
Mon May  7 09:06:35 2007  recovered 38 nontrivial dependencies
Mon May  7 09:06:35 2007  c205 factor: 1239933213047612666105646898805318952130080877894133506922312417689891534360814588585024998064920593215273393369005017406401346359167831352246502119380880242260898574629156714950720293624755668391314983709
Mon May  7 09:06:35 2007  elapsed time 41:12:51
Mon May  7 13:35:25 2007  
Mon May  7 13:35:25 2007  
Mon May  7 13:35:25 2007  Msieve v. 1.20
Mon May  7 13:35:25 2007  random seeds: 726193a7 b3edb83c
Mon May  7 13:35:25 2007  factoring 1239933213047612666105646898805318952130080877894133506922312417689891534360814588585024998064920593215273393369005017406401346359167831352246502119380880242260898574629156714950720293624755668391314983709 (205 digits)
Mon May  7 13:35:26 2007  commencing number field sieve (204-digit input)
Mon May  7 13:35:26 2007  R0: -497745340030349688137123548984527587890625
Mon May  7 13:35:26 2007  R1:  688579136852433871931703296
Mon May  7 13:35:26 2007  A0:  1
Mon May  7 13:35:26 2007  A1:  0
Mon May  7 13:35:26 2007  A2:  0
Mon May  7 13:35:26 2007  A3:  0
Mon May  7 13:35:26 2007  A4:  0
Mon May  7 13:35:26 2007  A5:  65
Mon May  7 13:35:26 2007  size score = 2.838529e-14, Murphy alpha = -0.309606, combined = 3.147120e-14
Mon May  7 13:35:26 2007  
Mon May  7 13:35:26 2007  commencing square root phase
Mon May  7 13:35:26 2007  reading relations for dependency 1
Mon May  7 13:35:29 2007  read 1361780 cycles
Mon May  7 13:35:33 2007  cycles contain 4449932 unique relations
Mon May  7 13:38:55 2007  read 4449932 relations
Mon May  7 13:39:21 2007  algebraic side is not a square!
Mon May  7 13:39:21 2007  reading relations for dependency 2
Mon May  7 13:39:28 2007  read 1362911 cycles
Mon May  7 13:39:33 2007  cycles contain 4452823 unique relations
Mon May  7 13:42:55 2007  read 4452823 relations
Mon May  7 13:43:38 2007  multiplying 6590240 relations
Mon May  7 14:04:39 2007  multiply complete, coefficients have about 194.54 million bits
Mon May  7 14:04:45 2007  initial square root is modulo 9581311
Mon May  7 14:44:28 2007  reading relations for dependency 3
Mon May  7 14:44:34 2007  read 1361360 cycles
Mon May  7 14:44:39 2007  cycles contain 4449434 unique relations
Mon May  7 14:47:59 2007  read 4449434 relations
Mon May  7 14:48:43 2007  multiplying 6580584 relations
Mon May  7 15:09:46 2007  multiply complete, coefficients have about 194.25 million bits
Mon May  7 15:09:52 2007  initial square root is modulo 9359971
Mon May  7 15:49:10 2007  prp86 factor: 14727009300836005774747192040091104486924254681038898244932636460938666209082366390921
Mon May  7 15:49:10 2007  prp119 factor: 84194501933072424710673247726080339489972024243058025972196143657445106326116344829664947434127977311892113511889207029
Mon May  7 15:49:10 2007  elapsed time 02:13:45

[frmky]

Originally Posted by jasonp

It's interesting that Sander's factorization only came up with 5 dependencies and yours came up with zero; I've never seen the NFS linear algebra come up with less than ~40 dependencies before now.

I looked back at the log files for several largish (185+ digit difficulty) SNFS jobs I've completed, and none of them had less than 40 dependencies. I'll watch out for that for the ones I complete in the near future.

52m269.log:Tue May  1 19:14:24 2007  recovered 49 nontrivial dependencies
53p269.log:Mon Apr 30 07:46:55 2007  recovered 44 nontrivial dependencies
54m271.log:Sat May  5 13:27:02 2007  recovered 47 nontrivial dependencies
54p269.log:Thu May  3 11:15:24 2007  recovered 50 nontrivial dependencies
32m485.log:Wed Apr 25 17:00:17 2007  recovered 47 nontrivial dependencies
53m269.log:Sat Apr 28 21:23:29 2007  recovered 45 nontrivial dependencies
54m263.log:Mon Apr 16 04:49:14 2007  recovered 45 nontrivial dependencies
65p241.log:Thu Apr 26 23:50:47 2007  recovered 47 nontrivial dependencies
msieve.log:Fri Apr 20 06:49:38 2007  recovered 47 nontrivial dependencies
msieve1.log:Wed Apr 11 20:17:56 2007  recovered 46 nontrivial dependencies

Greg

[jasonp]

Originally Posted by frmky

The C211-difficulty SNFS finished successfully on the third dependency. The log is below. Jason: I sent you a PM with the address where you can download the relations. Let me know if you got them ok.

I got them. It's great that things worked without trouble, though I'm not sure why the first dependency would have gotten corrupted. Actually, v1.21 will include a fix in the factor base generation that could have caused this to happen.

I was also worried that the FFT code would fail due to roundoff error when the square root involves such huge polynomial coefficients, but it seems to work out just fine. Each dependency only needs a few dozen multiplies at the highest precision, and the result is checked modulo a 1-word prime, so as long as failure due to roundoff error is rare most of the dependencies should lead to a congruence of squares.

From what I understand, these jobs are a little more than half the size of a 512-bit RSA number.

jasonp

[smh]

Originally Posted by jasonp

That would be helpful, thanks.

This time it found 47 non trivial dependencies.

I do run into problems with another number though:

Tue May 08 09:58:29 2007  Msieve v. 1.20
Tue May 08 09:58:29 2007  random seeds: 4e767a80 2211365f
Tue May 08 09:58:29 2007  factoring 84529300931687285552630442729603016602665796449004992350040538372463967451957369418772530670999505775101719581 (110 digits)
Tue May 08 09:58:30 2007  commencing number field sieve (110-digit input)
Tue May 08 09:58:30 2007  R0:  3172169114198268924301601144832
Tue May 08 09:58:30 2007  R1: -1
Tue May 08 09:58:30 2007  A0:  1
Tue May 08 09:58:30 2007  A1:  0
Tue May 08 09:58:30 2007  A2:  108
Tue May 08 09:58:30 2007  A3:  0
Tue May 08 09:58:30 2007  A4:  11664
Tue May 08 09:58:30 2007  size score = 2.894565e-013, Murphy alpha = 0.374636, combined = 2.491738e-013
Tue May 08 09:58:35 2007  restarting with 1503898 relations
Tue May 08 09:58:35 2007  generating factor base
Tue May 08 09:58:35 2007  factor base complete:
Tue May 08 09:58:35 2007  49098 rational roots (max prime = 599999)
Tue May 08 09:58:35 2007  48894 algebraic roots (max prime = 599941)
Tue May 08 09:58:35 2007  added 12223 free relations
Tue May 08 09:58:35 2007  
Tue May 08 09:58:35 2007  commencing relation filtering
Tue May 08 09:58:35 2007  commencing duplicate removal, pass 1
Tue May 08 09:58:48 2007  found 178064 hash collisions in 1516121 relations
Tue May 08 09:58:48 2007  commencing duplicate removal, pass 2
Tue May 08 09:58:52 2007  found 174764 duplicates and 1341357 unique relations
Tue May 08 09:58:52 2007  memory use: 39.7 MB
Tue May 08 09:58:52 2007  ignoring smallest 78641 rational and 78406 algebraic ideals
Tue May 08 09:58:52 2007  filtering rational ideals above 1001878
Tue May 08 09:58:52 2007  filtering algebraic ideals above 1001878
Tue May 08 09:58:52 2007  need 345503 more relations than ideals
Tue May 08 09:58:52 2007  commencing singleton removal, pass 1
Tue May 08 09:59:05 2007  relations with 0 large ideals: 50480
Tue May 08 09:59:05 2007  relations with 1 large ideals: 285872
Tue May 08 09:59:05 2007  relations with 2 large ideals: 590916
Tue May 08 09:59:05 2007  relations with 3 large ideals: 357008
Tue May 08 09:59:05 2007  relations with 4 large ideals: 55237
Tue May 08 09:59:05 2007  relations with 5 large ideals: 1844
Tue May 08 09:59:05 2007  relations with 6 large ideals: 0
Tue May 08 09:59:05 2007  relations with 7+ large ideals: 0
Tue May 08 09:59:05 2007  1341357 relations and about 1281792 large ideals
Tue May 08 09:59:05 2007  commencing singleton removal, pass 2
Tue May 08 09:59:20 2007  found 750120 singletons
Tue May 08 09:59:20 2007  current dataset: 591237 relations and about 376297 large ideals
Tue May 08 09:59:20 2007  commencing singleton removal, pass 3
Tue May 08 09:59:28 2007  found 88140 singletons
Tue May 08 09:59:28 2007  current dataset: 503097 relations and about 284155 large ideals
Tue May 08 09:59:28 2007  commencing singleton removal, final pass
Tue May 08 09:59:35 2007  memory use: 19.1 MB
Tue May 08 09:59:35 2007  commencing in-memory singleton removal
Tue May 08 09:59:35 2007  begin with 503097 relations and 290471 unique ideals
Tue May 08 09:59:35 2007  reduce to 473985 relations and 261026 ideals in 8 passes
Tue May 08 09:59:35 2007  max relations containing the same ideal: 18
Tue May 08 09:59:35 2007  not enough excess, attempting to create matrix anyway
Tue May 08 09:59:35 2007  ignoring smallest 78641 rational and 78406 algebraic ideals
Tue May 08 09:59:35 2007  filtering rational ideals above 1001878
Tue May 08 09:59:35 2007  filtering algebraic ideals above 1001878
Tue May 08 09:59:35 2007  need 180604 more relations than ideals
Tue May 08 09:59:35 2007  commencing singleton removal, final pass
Tue May 08 09:59:41 2007  memory use: 19.1 MB
Tue May 08 09:59:41 2007  commencing in-memory singleton removal
Tue May 08 09:59:41 2007  begin with 503097 relations and 290471 unique ideals
Tue May 08 09:59:41 2007  reduce to 473985 relations and 261026 ideals in 8 passes
Tue May 08 09:59:41 2007  max relations containing the same ideal: 18
Tue May 08 09:59:41 2007  removing 65285 relations and 49108 ideals in 16177 cliques
Tue May 08 09:59:41 2007  commencing in-memory singleton removal
Tue May 08 09:59:41 2007  begin with 408700 relations and 261026 unique ideals
Tue May 08 09:59:41 2007  reduce to 406044 relations and 209165 ideals in 5 passes
Tue May 08 09:59:41 2007  max relations containing the same ideal: 17
Tue May 08 09:59:42 2007  removing 49934 relations and 33757 ideals in 16177 cliques
Tue May 08 09:59:42 2007  commencing in-memory singleton removal
Tue May 08 09:59:42 2007  begin with 356110 relations and 209165 unique ideals
Tue May 08 09:59:42 2007  reduce to 354143 relations and 173375 ideals in 4 passes
Tue May 08 09:59:42 2007  max relations containing the same ideal: 17
Tue May 08 09:59:42 2007  removing 839 relations and 676 ideals in 163 cliques
Tue May 08 09:59:42 2007  commencing in-memory singleton removal
Tue May 08 09:59:42 2007  begin with 353304 relations and 173375 unique ideals
Tue May 08 09:59:42 2007  reduce to 353302 relations and 172697 ideals in 2 passes
Tue May 08 09:59:42 2007  max relations containing the same ideal: 17
Tue May 08 09:59:42 2007  relations with 0 large ideals: 50480
Tue May 08 09:59:42 2007  relations with 1 large ideals: 126595
Tue May 08 09:59:42 2007  relations with 2 large ideals: 122471
Tue May 08 09:59:42 2007  relations with 3 large ideals: 46833
Tue May 08 09:59:42 2007  relations with 4 large ideals: 6659
Tue May 08 09:59:42 2007  relations with 5 large ideals: 264
Tue May 08 09:59:42 2007  relations with 6 large ideals: 0
Tue May 08 09:59:42 2007  relations with 7+ large ideals: 0
Tue May 08 09:59:42 2007  commencing 2-way merge
Tue May 08 09:59:42 2007  merged 86296 relations
Tue May 08 09:59:42 2007  reduce to 267006 relation sets and 86401 unique ideals
Tue May 08 09:59:42 2007  commencing full merge
Tue May 08 09:59:43 2007  found 180606 cycles, need 157127
Tue May 08 09:59:43 2007  weight of 157127 cycles is about 5154793 (32.81/cycle)
Tue May 08 09:59:43 2007  distribution of cycle lengths:
Tue May 08 09:59:43 2007  1 relations: 50480
Tue May 08 09:59:43 2007  2 relations: 28379
Tue May 08 09:59:43 2007  3 relations: 24479
Tue May 08 09:59:43 2007  4 relations: 20014
Tue May 08 09:59:43 2007  5 relations: 15938
Tue May 08 09:59:43 2007  6 relations: 11228
Tue May 08 09:59:43 2007  7 relations: 6393
Tue May 08 09:59:43 2007  8 relations: 216
Tue May 08 09:59:43 2007  9 relations: 0
Tue May 08 09:59:43 2007  10+ relations: 0
Tue May 08 09:59:43 2007  heaviest cycle: 8 relations
Tue May 08 09:59:43 2007  commencing cycle optimization
Tue May 08 09:59:43 2007  start with 454268 relations
Tue May 08 09:59:44 2007  pruned 11955 relations
Tue May 08 09:59:44 2007  distribution of cycle lengths:
Tue May 08 09:59:44 2007  1 relations: 50480
Tue May 08 09:59:44 2007  2 relations: 29216
Tue May 08 09:59:44 2007  3 relations: 25837
Tue May 08 09:59:44 2007  4 relations: 20936
Tue May 08 09:59:44 2007  5 relations: 16276
Tue May 08 09:59:44 2007  6 relations: 10018
Tue May 08 09:59:44 2007  7 relations: 4254
Tue May 08 09:59:44 2007  8 relations: 110
Tue May 08 09:59:44 2007  9 relations: 0
Tue May 08 09:59:44 2007  10+ relations: 0
Tue May 08 09:59:44 2007  heaviest cycle: 8 relations
Tue May 08 09:59:44 2007  
Tue May 08 09:59:44 2007  commencing linear algebra
Tue May 08 09:59:44 2007  factor base loaded:
Tue May 08 09:59:44 2007  49098 rational ideals (max prime = 599999)
Tue May 08 09:59:44 2007  48894 algebraic ideals (max prime = 599941)
Tue May 08 09:59:44 2007  read 157127 cycles
Tue May 08 09:59:44 2007  cycles contain 295714 unique relations
Tue May 08 09:59:50 2007  read 295714 relations
Tue May 08 09:59:50 2007  using 32 quadratic characters above 33541478
Tue May 08 09:59:57 2007  matrix is 156245 x 157127 with weight 8407486 (avg 53.51/col)
Tue May 08 09:59:58 2007  filtering completed in 3 passes
Tue May 08 09:59:58 2007  matrix is 153211 x 153291 with weight 8151080 (avg 53.17/col)
Tue May 08 09:59:58 2007  saving the first 48 matrix rows for later
Tue May 08 09:59:58 2007  matrix is 153163 x 153291 with weight 5181021 (avg 33.80/col)
Tue May 08 09:59:58 2007  matrix includes 64 packed rows
Tue May 08 09:59:58 2007  using block size 61316 for processor cache size 4096 kB
Tue May 08 10:02:16 2007  lanczos error: not all columns used
Tue May 08 10:02:16 2007  lanczos halted after 2422 iterations
Tue May 08 10:02:16 2007  linear algebra failed; retrying...
Tue May 08 10:04:24 2007  lanczos halted after 2423 iterations
Tue May 08 10:04:24 2007  recovered 45 nontrivial dependencies
Tue May 08 10:04:24 2007  
Tue May 08 10:04:24 2007  commencing square root phase
Tue May 08 10:04:24 2007  reading relations for dependency 1
Tue May 08 10:04:24 2007  read 76604 cycles
Tue May 08 10:04:25 2007  cycles contain 164788 unique relations
Tue May 08 10:04:29 2007  read 164788 relations
Tue May 08 10:04:30 2007  multiplying 213574 relations
Tue May 08 10:04:43 2007  multiply complete, coefficients have about 6.75 million bits
Tue May 08 10:04:43 2007  error: cannot find an irreducible prime
Tue May 08 10:04:43 2007  error: relation product is incorrect
Tue May 08 10:04:43 2007  algebraic square root failed
Tue May 08 10:04:43 2007  reading relations for dependency 2
Tue May 08 10:04:43 2007  read 76679 cycles
Tue May 08 10:04:43 2007  cycles contain 165201 unique relations
Tue May 08 10:04:48 2007  read 165201 relations
Tue May 08 10:04:48 2007  multiplying 213842 relations
Tue May 08 10:05:01 2007  multiply complete, coefficients have about 6.76 million bits
Tue May 08 10:05:01 2007  error: cannot find an irreducible prime
Tue May 08 10:05:01 2007  error: relation product is incorrect
Tue May 08 10:05:01 2007  algebraic square root failed

It fails for all other dependencies.
The first lanczos resulted in an error.