Running Msieve - Page 5

jasonp · 2007-05-08, 13:35

Quote:

Originally Posted by smh

This time it found 47 non trivial dependencies.

I do run into problems with another number though:
[...]
It fails for all other dependencies.
The first lanczos resulted in an error.

I've noticed other cases where the lanczos iteration fails at the very last minute. It's hard to believe that it's just a random failure, but I don't know what else it could be.

The failing for all dependencies is probably because the algebraic polynomial is reducible modulo all primes. I was hoping such cases were rare to the point of nonexistence, but that's clearly not the case. Buhler et. al. describe what to do in that case, I guess I should fix the code to try and handle it.

fivemack · 2007-05-08, 15:04

Quote:

Originally Posted by jasonp

The failing for all dependencies is probably because the algebraic polynomial is reducible modulo all primes. I was hoping such cases were rare to the point of nonexistence, but that's clearly not the case. Buhler et. al. describe what to do in that case, I guess I should fix the code to try and handle it.

They're not very common, but one of the easiest ways of producing them (the trick where it's reducible if any of A, B or AB is a quadratic residue, and one of them must be) turns out to be exactly what you get if you remove an x-y factor from x^5-y^5 as you do for homogeneous-Cunningham numbers.

Tom

jasonp · 2007-05-08, 16:00

Quote:

Originally Posted by fivemack

They're not very common, but one of the easiest ways of producing them (the trick where it's reducible if any of A, B or AB is a quadratic residue, and one of them must be) turns out to be exactly what you get if you remove an x-y factor from x^5-y^5 as you do for homogeneous-Cunningham numbers.

Tom

Hmm, the standard way of dealing with them seems to be 'pick a prime q for which (degree d algebraic poly 'f') mod q has no linear factors in the galois field with q^d elements, and proceed like normal'. I guess the idea is that each relation is relatively prime to q (since each relation is a linear polynomial in the number field) and if f is squarefree then f mod q has at most floor(d/2) polynomial roots, which means the Newton iteration will succeed and produce an algebraic square root only once every 2^floor(d/2) dependencies. Does anyone know if I got this wrong? The code changes are easy, but this solution isn't very satisfying.

frmky · 2007-05-08, 20:13

Quote:

Originally Posted by fivemack

They're not very common, but one of the easiest ways of producing them (the trick where it's reducible if any of A, B or AB is a quadratic residue, and one of them must be) turns out to be exactly what you get if you remove an x-y factor from x^5-y^5 as you do for homogeneous-Cunningham numbers.

Tom

I completed 3^485-2^485 with msieve not long ago. Here's the log from that run. I no longer have the relations.

Code:

Tue Apr 24 23:08:49 2007  
Tue Apr 24 23:08:49 2007  
Tue Apr 24 23:08:49 2007  Msieve v. 1.19
Tue Apr 24 23:08:49 2007  random seeds: d5419339 461a4137
Tue Apr 24 23:08:49 2007  factoring 6775409496741484222042374795040084919902858241124182973562718124488754076805736701649393265379381343566191616830702282598445592041946094127667006214808880552531 (160 digits)
Tue Apr 24 23:08:49 2007  commencing number field sieve (160-digit input)
Tue Apr 24 23:08:49 2007  R0: -19088056323407827075424486287615602692670648963
Tue Apr 24 23:08:49 2007  R1:  158456325028528675187087900672
Tue Apr 24 23:08:49 2007  A0:  1
Tue Apr 24 23:08:49 2007  A1:  1
Tue Apr 24 23:08:49 2007  A2:  1
Tue Apr 24 23:08:49 2007  A3:  1
Tue Apr 24 23:08:49 2007  A4:  1
Tue Apr 24 23:08:49 2007  size score = 1.556255e-18, Murphy alpha = 1.718037, combined = 7.827576e-19
Tue Apr 24 23:08:54 2007  restarting with 13521796 relations
Tue Apr 24 23:08:54 2007  
Tue Apr 24 23:08:54 2007  commencing relation filtering
Tue Apr 24 23:08:54 2007  commencing duplicate removal, pass 1
Tue Apr 24 23:09:03 2007  error -10 reading relation 1052975
Tue Apr 24 23:10:04 2007  error -10 reading relation 7921055
Tue Apr 24 23:10:21 2007  error -4 reading relation 9437663
Tue Apr 24 23:10:57 2007  found 3606826 hash collisions in 13521793 relations
Tue Apr 24 23:10:57 2007  commencing duplicate removal, pass 2
Tue Apr 24 23:11:09 2007  found 3419230 duplicates and 10102563 unique relations
Tue Apr 24 23:11:09 2007  memory use: 94.6 MB
Tue Apr 24 23:11:12 2007  ignoring smallest 477764 rational and 477573 algebraic ideals
Tue Apr 24 23:11:12 2007  filtering rational ideals above 7017814
Tue Apr 24 23:11:12 2007  filtering algebraic ideals above 7017814
Tue Apr 24 23:11:12 2007  need 2101741 more relations than ideals
Tue Apr 24 23:11:12 2007  commencing singleton removal, pass 1
Tue Apr 24 23:12:51 2007  relations with 0 large ideals: 119521
Tue Apr 24 23:12:51 2007  relations with 1 large ideals: 253223
Tue Apr 24 23:12:51 2007  relations with 2 large ideals: 1528258
Tue Apr 24 23:12:51 2007  relations with 3 large ideals: 3236788
Tue Apr 24 23:12:51 2007  relations with 4 large ideals: 3017386
Tue Apr 24 23:12:51 2007  relations with 5 large ideals: 1494982
Tue Apr 24 23:12:51 2007  relations with 6 large ideals: 388655
Tue Apr 24 23:12:51 2007  relations with 7+ large ideals: 63750
Tue Apr 24 23:12:51 2007  10102563 relations and about 8741882 large ideals
Tue Apr 24 23:12:51 2007  commencing singleton removal, pass 2
Tue Apr 24 23:14:30 2007  found 3017713 singletons
Tue Apr 24 23:14:30 2007  current dataset: 7084850 relations and about 5429554 large ideals
Tue Apr 24 23:14:31 2007  commencing singleton removal, pass 3
Tue Apr 24 23:15:43 2007  found 406081 singletons
Tue Apr 24 23:15:43 2007  current dataset: 6678769 relations and about 5015667 large ideals
Tue Apr 24 23:15:43 2007  commencing singleton removal, pass 4
Tue Apr 24 23:16:51 2007  found 69895 singletons
Tue Apr 24 23:16:51 2007  current dataset: 6608874 relations and about 4945502 large ideals
Tue Apr 24 23:16:51 2007  commencing singleton removal, final pass
Tue Apr 24 23:18:04 2007  memory use: 279.5 MB
Tue Apr 24 23:18:04 2007  commencing in-memory singleton removal
Tue Apr 24 23:18:05 2007  begin with 6608874 relations and 5463511 unique ideals
Tue Apr 24 23:18:13 2007  reduce to 5966991 relations and 4809011 ideals in 9 passes
Tue Apr 24 23:18:13 2007  max relations containing the same ideal: 31
Tue Apr 24 23:18:14 2007  not enough excess, attempting to create matrix anyway
Tue Apr 24 23:18:14 2007  ignoring smallest 477764 rational and 477573 algebraic ideals
Tue Apr 24 23:18:14 2007  filtering rational ideals above 7017814
Tue Apr 24 23:18:14 2007  filtering algebraic ideals above 7017814
Tue Apr 24 23:18:14 2007  need 1098637 more relations than ideals
Tue Apr 24 23:18:14 2007  commencing singleton removal, final pass
Tue Apr 24 23:19:27 2007  memory use: 279.5 MB
Tue Apr 24 23:19:27 2007  commencing in-memory singleton removal
Tue Apr 24 23:19:28 2007  begin with 6608874 relations and 5463511 unique ideals
Tue Apr 24 23:19:36 2007  reduce to 5966991 relations and 4809011 ideals in 9 passes
Tue Apr 24 23:19:36 2007  max relations containing the same ideal: 31
Tue Apr 24 23:19:39 2007  removing 202503 relations and 172832 ideals in 29671 cliques
Tue Apr 24 23:19:40 2007  commencing in-memory singleton removal
Tue Apr 24 23:19:40 2007  begin with 5764488 relations and 4809011 unique ideals
Tue Apr 24 23:19:45 2007  reduce to 5760851 relations and 4632531 ideals in 6 passes
Tue Apr 24 23:19:45 2007  max relations containing the same ideal: 29
Tue Apr 24 23:19:49 2007  removing 155789 relations and 126118 ideals in 29671 cliques
Tue Apr 24 23:19:49 2007  commencing in-memory singleton removal
Tue Apr 24 23:19:50 2007  begin with 5605062 relations and 4632531 unique ideals
Tue Apr 24 23:19:54 2007  reduce to 5602525 relations and 4503864 ideals in 5 passes
Tue Apr 24 23:19:54 2007  max relations containing the same ideal: 29
Tue Apr 24 23:19:56 2007  relations with 0 large ideals: 119521
Tue Apr 24 23:19:56 2007  relations with 1 large ideals: 243537
Tue Apr 24 23:19:56 2007  relations with 2 large ideals: 1053613
Tue Apr 24 23:19:56 2007  relations with 3 large ideals: 1762934
Tue Apr 24 23:19:56 2007  relations with 4 large ideals: 1482356
Tue Apr 24 23:19:56 2007  relations with 5 large ideals: 729448
Tue Apr 24 23:19:56 2007  relations with 6 large ideals: 181507
Tue Apr 24 23:19:56 2007  relations with 7+ large ideals: 29609
Tue Apr 24 23:19:56 2007  commencing 2-way merge
Tue Apr 24 23:20:00 2007  merged 1516168 relations
Tue Apr 24 23:20:02 2007  reduce to 4086357 relation sets and 2987696 unique ideals
Tue Apr 24 23:20:02 2007  commencing full merge
Tue Apr 24 23:26:29 2007  found 1878973 cycles, need 1778776
Tue Apr 24 23:26:30 2007  weight of 1778776 cycles is about 146427573 (82.32/cycle)
Tue Apr 24 23:26:30 2007  distribution of cycle lengths:
Tue Apr 24 23:26:30 2007  1 relations: 168089
Tue Apr 24 23:26:30 2007  2 relations: 144617
Tue Apr 24 23:26:30 2007  3 relations: 175341
Tue Apr 24 23:26:30 2007  4 relations: 181203
Tue Apr 24 23:26:30 2007  5 relations: 177965
Tue Apr 24 23:26:30 2007  6 relations: 164892
Tue Apr 24 23:26:30 2007  7 relations: 147097
Tue Apr 24 23:26:30 2007  8 relations: 129367
Tue Apr 24 23:26:30 2007  9 relations: 110942
Tue Apr 24 23:26:30 2007  10+ relations: 379263
Tue Apr 24 23:26:30 2007  heaviest cycle: 19 relations
Tue Apr 24 23:26:30 2007  commencing cycle optimization
Tue Apr 24 23:28:53 2007  start with 11213349 relations
Tue Apr 24 23:29:44 2007  pruned 248657 relations
Tue Apr 24 23:29:45 2007  distribution of cycle lengths:
Tue Apr 24 23:29:46 2007  1 relations: 168089
Tue Apr 24 23:29:46 2007  2 relations: 146734
Tue Apr 24 23:29:46 2007  3 relations: 180052
Tue Apr 24 23:29:47 2007  4 relations: 185154
Tue Apr 24 23:29:47 2007  5 relations: 183750
Tue Apr 24 23:29:47 2007  6 relations: 168686
Tue Apr 24 23:29:47 2007  7 relations: 151065
Tue Apr 24 23:29:47 2007  8 relations: 131521
Tue Apr 24 23:29:47 2007  9 relations: 112035
Tue Apr 24 23:29:47 2007  10+ relations: 351690
Tue Apr 24 23:29:47 2007  heaviest cycle: 19 relations
Tue Apr 24 23:29:47 2007  
Tue Apr 24 23:29:48 2007  commencing linear algebra
Tue Apr 24 23:29:54 2007  factor base loaded:
Tue Apr 24 23:29:54 2007  910077 rational ideals (max prime = 13999981)
Tue Apr 24 23:29:54 2007  664417 algebraic ideals (max prime = 9999991)
Tue Apr 24 23:30:02 2007  read 1778776 cycles
Tue Apr 24 23:30:08 2007  cycles contain 5078685 unique relations
Tue Apr 24 23:31:14 2007  read 5078685 relations
Tue Apr 24 23:31:25 2007  using 32 quadratic characters above 134216042
Tue Apr 24 23:37:49 2007  matrix is 1778696 x 1778776 with weight 186388818 (avg 104.78/col)
Tue Apr 24 23:38:04 2007  filtering completed in 2 passes
Tue Apr 24 23:38:05 2007  matrix is 1778170 x 1778250 with weight 186335355 (avg 104.79/col)
Tue Apr 24 23:38:24 2007  saving the first 48 matrix rows for later
Tue Apr 24 23:38:28 2007  matrix is 1778122 x 1778250 with weight 147590134 (avg 83.00/col)
Tue Apr 24 23:38:28 2007  matrix includes 64 packed rows
Tue Apr 24 23:38:29 2007  using block size 43690 for processor cache size 1024 kB
Wed Apr 25 17:00:10 2007  lanczos halted after 28120 iterations
Wed Apr 25 17:00:17 2007  recovered 47 nontrivial dependencies
Wed Apr 25 17:00:17 2007  
Wed Apr 25 17:00:17 2007  commencing square root phase
Wed Apr 25 17:00:17 2007  reading relations for dependency 1
Wed Apr 25 17:00:19 2007  read 888244 cycles
Wed Apr 25 17:00:22 2007  cycles contain 3273058 unique relations
Wed Apr 25 17:01:33 2007  read 3273058 relations
Wed Apr 25 17:02:01 2007  multiplying 5471154 relations
Wed Apr 25 17:10:32 2007  multiply complete, coefficients have about 128.73 million bits
Wed Apr 25 17:10:36 2007  initial square root is modulo 1738440733
Wed Apr 25 17:26:19 2007  prp78 factor: 149584932408455850469686638700894136361166377323405964836399786094547275251201
Wed Apr 25 17:26:19 2007  prp83 factor: 45294732481748801706930801406824920716844684954263316680862047774443547180836405331
Wed Apr 25 17:26:19 2007  elapsed time 18:17:30

Greg

jasonp · 2007-05-11, 16:19

Quote:

Originally Posted by smh

I do run into problems with another number though:
[...]
It fails for all other dependencies.
The first lanczos resulted in an error.

I've made the changes so that this factorization completes successfully. Do you need the factors? (They're at home now)

smh · 2007-05-12, 12:30

Quote:

Originally Posted by jasonp

PS: @smh:
Fri May 11 10:52:36 2007 prp49 factor: 6214371966272720891412679817612071803187468972909
Fri May 11 10:52:40 2007 prp62 factor: 13602227447995293360238994329010469074018220326044935134602609

Thanks, but i had them already. I'll give the new version a try later this weekend.

JHansen · 2007-05-17, 09:45

I sieved a C120 with Franke's lattice siever. I get a segfault right as the linear algebra is about to start. I'm using a Windows XP Intel Core2 Duo system, msieve v.1.21.

Code:

Thu May 17 10:53:22 2007  
Thu May 17 10:53:22 2007  
Thu May 17 10:53:22 2007  Msieve v. 1.21
Thu May 17 10:53:22 2007  random seeds: f0cf55d8 1c033f40
Thu May 17 10:53:22 2007  factoring 419623832897771350700010781466963547592960694394751245814861806724281650265191070069221647901484064031010752997237754619 (120 digits)
Thu May 17 10:53:22 2007  commencing number field sieve (120-digit input)
Thu May 17 10:53:23 2007  R0: -143733799094117939873204
Thu May 17 10:53:23 2007  R1:  1571675241229
Thu May 17 10:53:23 2007  A0: -13301770869023917069542383757
Thu May 17 10:53:23 2007  A1: -3354843473866079084112555
Thu May 17 10:53:23 2007  A2: -86225108642303173709
Thu May 17 10:53:23 2007  A3:  180020813747795
Thu May 17 10:53:23 2007  A4:  13713426042
Thu May 17 10:53:23 2007  A5:  6840
Thu May 17 10:53:23 2007  size score = 2.310744e-012, Murphy alpha = -5.882862, combined = 1.642038e-011
Thu May 17 10:54:30 2007  restarting with 11439640 relations
Thu May 17 10:54:30 2007  
Thu May 17 10:54:30 2007  commencing relation filtering
Thu May 17 10:54:30 2007  commencing duplicate removal, pass 1
Thu May 17 10:54:51 2007  error -8 reading relation 1953368
Thu May 17 10:55:09 2007  error -14 reading relation 3649203
Thu May 17 10:55:24 2007  error -1 reading relation 5007053
Thu May 17 10:55:38 2007  error -14 reading relation 6285657
Thu May 17 10:56:35 2007  found 2336237 hash collisions in 11439636 relations
Thu May 17 10:56:35 2007  commencing duplicate removal, pass 2
Thu May 17 10:57:07 2007  found 2177677 duplicates and 9261959 unique relations
Thu May 17 10:57:07 2007  memory use: 65.3 MB
Thu May 17 10:57:10 2007  ignoring smallest 338783 rational and 338440 algebraic ideals
Thu May 17 10:57:10 2007  filtering rational ideals above 4851242
Thu May 17 10:57:10 2007  filtering algebraic ideals above 4851242
Thu May 17 10:57:10 2007  need 1151279 more relations than ideals
Thu May 17 10:57:10 2007  commencing singleton removal, pass 1
Thu May 17 10:58:58 2007  relations with 0 large ideals: 91070
Thu May 17 10:58:58 2007  relations with 1 large ideals: 725678
Thu May 17 10:58:58 2007  relations with 2 large ideals: 2235162
Thu May 17 10:58:58 2007  relations with 3 large ideals: 3288920
Thu May 17 10:58:58 2007  relations with 4 large ideals: 2319517
Thu May 17 10:58:58 2007  relations with 5 large ideals: 601612
Thu May 17 10:58:58 2007  relations with 6 large ideals: 0
Thu May 17 10:58:58 2007  relations with 7+ large ideals: 0
Thu May 17 10:58:58 2007  9261959 relations and about 8108366 large ideals
Thu May 17 10:58:58 2007  commencing singleton removal, pass 2
Thu May 17 11:00:46 2007  found 3638953 singletons
Thu May 17 11:00:46 2007  current dataset: 5623006 relations and about 3984646 large ideals
Thu May 17 11:00:46 2007  commencing singleton removal, pass 3
Thu May 17 11:01:58 2007  found 556127 singletons
Thu May 17 11:01:58 2007  current dataset: 5066879 relations and about 3409173 large ideals
Thu May 17 11:01:58 2007  commencing singleton removal, pass 4
Thu May 17 11:03:03 2007  found 107259 singletons
Thu May 17 11:03:03 2007  current dataset: 4959620 relations and about 3301026 large ideals
Thu May 17 11:03:03 2007  commencing singleton removal, pass 5
Thu May 17 11:04:07 2007  found 20725 singletons
Thu May 17 11:04:07 2007  current dataset: 4938895 relations and about 3280271 large ideals
Thu May 17 11:04:07 2007  commencing singleton removal, final pass
Thu May 17 11:05:14 2007  memory use: 176.8 MB
Thu May 17 11:05:14 2007  commencing in-memory singleton removal
Thu May 17 11:05:14 2007  begin with 4938895 relations and 3461211 unique ideals
Thu May 17 11:05:19 2007  reduce to 4628274 relations and 3147113 ideals in 9 passes
Thu May 17 11:05:19 2007  max relations containing the same ideal: 36
Thu May 17 11:05:21 2007  removing 736170 relations and 571229 ideals in 164941 cliques
Thu May 17 11:05:22 2007  commencing in-memory singleton removal
Thu May 17 11:05:22 2007  begin with 3892104 relations and 3147113 unique ideals
Thu May 17 11:05:25 2007  reduce to 3842661 relations and 2524643 ideals in 7 passes
Thu May 17 11:05:25 2007  max relations containing the same ideal: 31
Thu May 17 11:05:27 2007  removing 558806 relations and 393865 ideals in 164941 cliques
Thu May 17 11:05:27 2007  commencing in-memory singleton removal
Thu May 17 11:05:28 2007  begin with 3283855 relations and 2524643 unique ideals
Thu May 17 11:05:29 2007  reduce to 3244584 relations and 2090001 ideals in 6 passes
Thu May 17 11:05:29 2007  max relations containing the same ideal: 28
Thu May 17 11:05:31 2007  removing 19016 relations and 15713 ideals in 3303 cliques
Thu May 17 11:05:31 2007  commencing in-memory singleton removal
Thu May 17 11:05:32 2007  begin with 3225568 relations and 2090001 unique ideals
Thu May 17 11:05:33 2007  reduce to 3225525 relations and 2074245 ideals in 3 passes
Thu May 17 11:05:33 2007  max relations containing the same ideal: 28
Thu May 17 11:05:33 2007  dataset has 70.0% excess relations
Thu May 17 11:05:36 2007  ignoring smallest 307120 rational and 306973 algebraic ideals
Thu May 17 11:05:36 2007  filtering rational ideals above 4366117
Thu May 17 11:05:36 2007  filtering algebraic ideals above 4366117
Thu May 17 11:05:36 2007  need 1036152 more relations than ideals
Thu May 17 11:05:36 2007  commencing singleton removal, final pass
Thu May 17 11:06:22 2007  memory use: 116.0 MB
Thu May 17 11:06:22 2007  commencing in-memory singleton removal
Thu May 17 11:06:23 2007  begin with 3225525 relations and 2137132 unique ideals
Thu May 17 11:06:24 2007  reduce to 3223682 relations and 2135289 ideals in 5 passes
Thu May 17 11:06:24 2007  max relations containing the same ideal: 28
Thu May 17 11:06:26 2007  removing 105884 relations and 79764 ideals in 26120 cliques
Thu May 17 11:06:26 2007  commencing in-memory singleton removal
Thu May 17 11:06:26 2007  begin with 3117798 relations and 2135289 unique ideals
Thu May 17 11:06:27 2007  reduce to 3116160 relations and 2053874 ideals in 4 passes
Thu May 17 11:06:27 2007  max relations containing the same ideal: 27
Thu May 17 11:06:29 2007  removing 93115 relations and 66995 ideals in 26120 cliques
Thu May 17 11:06:29 2007  commencing in-memory singleton removal
Thu May 17 11:06:29 2007  begin with 3023045 relations and 2053874 unique ideals
Thu May 17 11:06:30 2007  reduce to 3021553 relations and 1985374 ideals in 4 passes
Thu May 17 11:06:30 2007  max relations containing the same ideal: 27
Thu May 17 11:06:31 2007  dataset has 53.0% excess relations
Thu May 17 11:06:33 2007  ignoring smallest 275335 rational and 274986 algebraic ideals
Thu May 17 11:06:33 2007  filtering rational ideals above 3880993
Thu May 17 11:06:33 2007  filtering algebraic ideals above 3880993
Thu May 17 11:06:33 2007  need 828943 more relations than ideals
Thu May 17 11:06:33 2007  commencing singleton removal, final pass
Thu May 17 11:07:17 2007  memory use: 93.5 MB
Thu May 17 11:07:17 2007  commencing in-memory singleton removal
Thu May 17 11:07:17 2007  begin with 3021553 relations and 2048999 unique ideals
Thu May 17 11:07:19 2007  reduce to 3020194 relations and 2047640 ideals in 4 passes
Thu May 17 11:07:19 2007  max relations containing the same ideal: 28
Thu May 17 11:07:20 2007  removing 221497 relations and 149692 ideals in 71805 cliques
Thu May 17 11:07:20 2007  commencing in-memory singleton removal
Thu May 17 11:07:20 2007  begin with 2798697 relations and 2047640 unique ideals
Thu May 17 11:07:22 2007  reduce to 2789471 relations and 1888525 ideals in 5 passes
Thu May 17 11:07:22 2007  max relations containing the same ideal: 28
Thu May 17 11:07:23 2007  removing 223916 relations and 152111 ideals in 71805 cliques
Thu May 17 11:07:23 2007  commencing in-memory singleton removal
Thu May 17 11:07:24 2007  begin with 2565555 relations and 1888525 unique ideals
Thu May 17 11:07:25 2007  reduce to 2556057 relations and 1726713 ideals in 6 passes
Thu May 17 11:07:25 2007  max relations containing the same ideal: 27
Thu May 17 11:07:26 2007  removing 2403 relations and 2003 ideals in 400 cliques
Thu May 17 11:07:26 2007  commencing in-memory singleton removal
Thu May 17 11:07:27 2007  begin with 2553654 relations and 1726713 unique ideals
Thu May 17 11:07:27 2007  reduce to 2553652 relations and 1724708 ideals in 2 passes
Thu May 17 11:07:27 2007  max relations containing the same ideal: 27
Thu May 17 11:07:28 2007  dataset has 22.4% excess relations
Thu May 17 11:07:30 2007  ignoring smallest 243263 rational and 243098 algebraic ideals
Thu May 17 11:07:30 2007  filtering rational ideals above 3395869
Thu May 17 11:07:30 2007  filtering algebraic ideals above 3395869
Thu May 17 11:07:30 2007  need 731400 more relations than ideals
Thu May 17 11:07:30 2007  commencing singleton removal, final pass
Thu May 17 11:08:10 2007  memory use: 93.5 MB
Thu May 17 11:08:10 2007  commencing in-memory singleton removal
Thu May 17 11:08:10 2007  begin with 2553652 relations and 1788491 unique ideals
Thu May 17 11:08:11 2007  reduce to 2552307 relations and 1787146 ideals in 4 passes
Thu May 17 11:08:11 2007  max relations containing the same ideal: 27
Thu May 17 11:08:12 2007  removing 64282 relations and 47402 ideals in 16880 cliques
Thu May 17 11:08:12 2007  commencing in-memory singleton removal
Thu May 17 11:08:12 2007  begin with 2488025 relations and 1787146 unique ideals
Thu May 17 11:08:13 2007  reduce to 2487156 relations and 1738871 ideals in 4 passes
Thu May 17 11:08:13 2007  max relations containing the same ideal: 27
Thu May 17 11:08:14 2007  removing 56648 relations and 39768 ideals in 16880 cliques
Thu May 17 11:08:14 2007  commencing in-memory singleton removal
Thu May 17 11:08:15 2007  begin with 2430508 relations and 1738871 unique ideals
Thu May 17 11:08:16 2007  reduce to 2429676 relations and 1698263 ideals in 4 passes
Thu May 17 11:08:16 2007  max relations containing the same ideal: 27
Thu May 17 11:08:16 2007  dataset has 8.0% excess relations
Thu May 17 11:08:16 2007  relations with 0 large ideals: 30057
Thu May 17 11:08:16 2007  relations with 1 large ideals: 228325
Thu May 17 11:08:16 2007  relations with 2 large ideals: 644709
Thu May 17 11:08:16 2007  relations with 3 large ideals: 832045
Thu May 17 11:08:16 2007  relations with 4 large ideals: 518572
Thu May 17 11:08:16 2007  relations with 5 large ideals: 153688
Thu May 17 11:08:16 2007  relations with 6 large ideals: 20918
Thu May 17 11:08:16 2007  relations with 7+ large ideals: 1362
Thu May 17 11:08:16 2007  commencing 2-way merge
Thu May 17 11:08:19 2007  merged 662028 relations
Thu May 17 11:08:19 2007  reduce to 1767648 relation sets and 1036235 unique ideals
Thu May 17 11:08:19 2007  commencing full merge
Thu May 17 11:08:50 2007  found 893193 cycles, need 650435
Thu May 17 11:08:50 2007  weight of 650435 cycles is about 42490350 (65.33/cycle)
Thu May 17 11:08:50 2007  distribution of cycle lengths:
Thu May 17 11:08:50 2007  1 relations: 50107
Thu May 17 11:08:50 2007  2 relations: 65048
Thu May 17 11:08:50 2007  3 relations: 71839
Thu May 17 11:08:50 2007  4 relations: 74919
Thu May 17 11:08:50 2007  5 relations: 75801
Thu May 17 11:08:50 2007  6 relations: 72704
Thu May 17 11:08:50 2007  7 relations: 69088
Thu May 17 11:08:50 2007  8 relations: 63713
Thu May 17 11:08:50 2007  9 relations: 55005
Thu May 17 11:08:50 2007  10+ relations: 52211
Thu May 17 11:08:50 2007  heaviest cycle: 12 relations
Thu May 17 11:08:50 2007  commencing cycle optimization
Thu May 17 11:08:51 2007  start with 3531925 relations
Thu May 17 11:08:59 2007  pruned 84381 relations
Thu May 17 11:08:59 2007  distribution of cycle lengths:
Thu May 17 11:08:59 2007  1 relations: 50107
Thu May 17 11:08:59 2007  2 relations: 66554
Thu May 17 11:08:59 2007  3 relations: 74763
Thu May 17 11:08:59 2007  4 relations: 77416
Thu May 17 11:08:59 2007  5 relations: 78905
Thu May 17 11:08:59 2007  6 relations: 75936
Thu May 17 11:08:59 2007  7 relations: 71944
Thu May 17 11:08:59 2007  8 relations: 63826
Thu May 17 11:08:59 2007  9 relations: 51154
Thu May 17 11:08:59 2007  10+ relations: 39830
Thu May 17 11:08:59 2007  heaviest cycle: 12 relations
Thu May 17 11:09:00 2007  
Thu May 17 11:09:00 2007  commencing linear algebra
Thu May 17 11:09:01 2007  factor base loaded:
Thu May 17 11:09:01 2007  330960 rational ideals (max prime = 4730729)
Thu May 17 11:09:01 2007  330651 algebraic ideals (max prime = 4730729)
Thu May 17 11:09:01 2007  read 650435 cycles
Thu May 17 11:09:03 2007  cycles contain 1753126 unique relations
Thu May 17 11:09:32 2007  read 1753126 relations
Thu May 17 11:09:35 2007  using 32 quadratic characters above 134215748
Thu May 17 11:44:32 2007

jasonp · 2007-05-17, 13:24

Quote:

Originally Posted by JHansen

I sieved a C120 with Franke's lattice siever. I get a segfault right as the linear algebra is about to start.

there was a bugfix in v1.21 that was incorrect

. On line 710 of gnfs/ffpoly.c, change

Code:

		for (j = 0; i <= f->degree; i++, j++) {
			f->coef[j] = f->coef[i];
		}

to

Code:

		for (j = i; i <= f->degree; i++) {
			f->coef[i - j] = f->coef[i];
		}

Tom, your last factorization attempt was probably bitten by this bug too.

jasonp

Andi47 · 2007-05-17, 15:50

Quote:

Originally Posted by jasonp

there was a bugfix in v1.21 that was incorrect

. On line 710 of gnfs/ffpoly.c, change

Code:

		for (j = 0; i <= f->degree; i++, j++) {
			f->coef[j] = f->coef[i];
		}

to

Code:

		for (j = i; i <= f->degree; i++) {
			f->coef[i - j] = f->coef[i];
		}

Tom, your last factorization attempt was probably bitten by this bug too.

jasonp

Can you please upload a 1.21b containing this fix for windows users?

smh · 2007-05-17, 18:41

Today i finished a deg. 4 SNFS diff. ~139 with msieve.

Sieving was done with GGNFS. I oversieved quite a bit, but msieve needed more relations.

After changing the SRTFBITS and SATFBITS to 46 (from the 47 used with GGNFS) msieve was able to build the matrix, which ran more than 4 times faster than GGNFS :-)

Factorization was found on the 7th dependency.

jasonp · 2007-05-17, 19:24

Quote:

Originally Posted by smh

Today i finished a deg. 4 SNFS diff. ~139 with msieve.

Sieving was done with GGNFS. I oversieved quite a bit, but msieve needed more relations.

After changing the SRTFBITS and SATFBITS to 46 (from the 47 used with GGNFS) msieve was able to build the matrix, which ran more than 4 times faster than GGNFS :-)

Factorization was found on the 7th dependency.

Good to hear. Could you PM me the logfile? If msieve did not do any sieving then changing S[RA]TFBITS shouldn't have had any effect. I would expect to have to lower S[RA]LPMAX though.

I'm most of the way through adding multithread support to the linear algebra, at least the basic kind. Depending on how smoothly it goes, I'll try to push out the next release tomorrow morning.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
error when running msieve 1.53 with cuda	aein	Msieve	9	2019-02-25 14:09
Help need to running Msieve	appleseed	Msieve	12	2016-04-10 02:31
Problem in running msieve with CUDA	mohamed	Msieve	20	2013-08-01 08:27
CUDA_ERROR_LAUNCH_OUT_OF_RESOURCES when running msieve 1.5.0 with CUDA	ryanp	Msieve	3	2012-06-12 03:27
Trouble Running Msieve	Sab	Msieve	4	2009-07-07 06:19

2007-05-17, 18:41	#54
smh "Sander" Oct 2002 52.345322,5.52471 29·41 Posts	Today i finished a deg. 4 SNFS diff. ~139 with msieve. Sieving was done with GGNFS. I oversieved quite a bit, but msieve needed more relations. After changing the SRTFBITS and SATFBITS to 46 (from the 47 used with GGNFS) msieve was able to build the matrix, which ran more than 4 times faster than GGNFS :-) Factorization was found on the 7th dependency.