MSieve oddities....

[schickel]

Jason, what are the odds of this happening:

Sat Mar 31 09:18:21 2007  Msieve v. 1.17
Sat Mar 31 09:18:21 2007  random seeds: 5b81797a 53bf75dc
Sat Mar 31 09:18:21 2007  factoring 32200965083893482185326001147284472219899155920246951448410850906541174123992621173 (83 digits)
Sat Mar 31 09:18:22 2007  commencing quadratic sieve (83-digit input)
{.... }
Sat Mar 31 13:17:55 2007  matrix is 52647 x 52770 with weight 1669376 (avg 31.63/col)
Sat Mar 31 13:17:59 2007  filtering completed in 4 passes
Sat Mar 31 13:18:00 2007  matrix is 44740 x 44804 with weight 1384785 (avg 30.91/col)
Sat Mar 31 13:18:03 2007  saving the first 48 matrix rows for later
Sat Mar 31 13:18:03 2007  matrix is 44692 x 44804 with weight 1007923 (avg 22.50/col)
Sat Mar 31 13:18:03 2007  matrix includes 32 packed rows
Sat Mar 31 13:22:31 2007  lanczos error: not all columns used
Sat Mar 31 13:22:31 2007  lanczos halted after 707 iterations
Sat Mar 31 13:22:31 2007  linear algebra failed; retrying...
Sat Mar 31 13:22:31 2007  saving the first 48 matrix rows for later
Sat Mar 31 13:22:31 2007  matrix is 44692 x 44804 with weight 777029 (avg 17.34/col)
Sat Mar 31 13:22:31 2007  matrix includes 32 packed rows
Sat Mar 31 13:26:42 2007  lanczos halted after 707 iterations
Sat Mar 31 13:26:44 2007  recovered 11 nontrivial dependencies
Sat Mar 31 13:26:50 2007  c83 factor: 32200965083893482185326001147284472219899155920246951448410850906541174123992621173
Sat Mar 31 13:26:50 2007  elapsed time 04:08:29

Twice?

Tue Apr 03 08:48:16 2007  Msieve v. 1.17
Tue Apr 03 08:48:16 2007  random seeds: a454aaf0 9f297949
Tue Apr 03 08:48:16 2007  factoring 21075296035900797161789357280557082902659396333534601045084652691867815920371245259118887103 (92 digits)
Tue Apr 03 08:48:17 2007  commencing quadratic sieve (92-digit input)
{ .... }
Tue Apr 03 11:17:28 2007  matrix is 67059 x 67459 with weight 3806940 (avg 56.43/col)
Tue Apr 03 11:17:28 2007  filtering completed in 4 passes
Tue Apr 03 11:17:28 2007  matrix is 65281 x 65345 with weight 3618563 (avg 55.38/col)
Tue Apr 03 11:17:29 2007  saving the first 48 matrix rows for later
Tue Apr 03 11:17:29 2007  matrix is 65233 x 65345 with weight 2683532 (avg 41.07/col)
Tue Apr 03 11:17:29 2007  matrix includes 32 packed rows
Tue Apr 03 11:20:54 2007  lanczos error: not all columns used
Tue Apr 03 11:20:54 2007  lanczos halted after 1033 iterations
Tue Apr 03 11:20:54 2007  linear algebra failed; retrying...
Tue Apr 03 11:20:54 2007  saving the first 48 matrix rows for later
Tue Apr 03 11:20:54 2007  matrix is 65233 x 65345 with weight 1932698 (avg 29.58/col)
Tue Apr 03 11:20:54 2007  matrix includes 32 packed rows
Tue Apr 03 11:24:01 2007  lanczos halted after 1032 iterations
Tue Apr 03 11:24:01 2007  recovered 11 nontrivial dependencies
Tue Apr 03 11:24:06 2007  c92 factor: 21075296035900797161789357280557082902659396333534601045084652691867815920371245259118887103
Tue Apr 03 11:24:06 2007  elapsed time 02:35:50

Luckily, they both factored out just by rerunning MSieve again on the same dat file.

Sat Mar 31 20:39:13 2007  matrix is 52647 x 52770 with weight 1669376 (avg 31.63/col)
Sat Mar 31 20:39:18 2007  filtering completed in 4 passes
Sat Mar 31 20:39:18 2007  matrix is 44740 x 44804 with weight 1384785 (avg 30.91/col)
Sat Mar 31 20:39:21 2007  saving the first 48 matrix rows for later
Sat Mar 31 20:39:22 2007  matrix is 44692 x 44804 with weight 1007923 (avg 22.50/col)
Sat Mar 31 20:39:22 2007  matrix includes 32 packed rows
Sat Mar 31 20:44:15 2007  lanczos halted after 708 iterations
Sat Mar 31 20:44:17 2007  recovered 12 nontrivial dependencies
Sat Mar 31 20:44:18 2007  prp41 factor: 32921344246694627905159036248848172735383
Sat Mar 31 20:44:18 2007  prp42 factor: 978118172897102362382329280406398275442131

Tue Apr 03 11:50:27 2007  matrix is 67059 x 67459 with weight 3806940 (avg 56.43/col)
Tue Apr 03 11:50:28 2007  filtering completed in 4 passes
Tue Apr 03 11:50:28 2007  matrix is 65281 x 65345 with weight 3618563 (avg 55.38/col)
Tue Apr 03 11:50:29 2007  saving the first 48 matrix rows for later
Tue Apr 03 11:50:29 2007  matrix is 65233 x 65345 with weight 2683532 (avg 41.07/col)
Tue Apr 03 11:50:29 2007  matrix includes 32 packed rows
Tue Apr 03 11:54:01 2007  lanczos halted after 1033 iterations
Tue Apr 03 11:54:02 2007  recovered 17 nontrivial dependencies
Tue Apr 03 11:54:04 2007  prp46 factor: 1155662819900477340596743106963448902784338557
Tue Apr 03 11:54:04 2007  prp47 factor: 18236544148504964911628354017925440534379782379

Later,
Frank

[jasonp]

Originally Posted by schickel

Jason, what are the odds of this happening:

Restarting the linear algebra can happen once in a while; the factorization not working afterwards is a bug that should be fixed in v1.18

jasonp

[schickel]

Jason,
Cool. I updated to 1.18 on one of my PCs, although I'll have to check the other one now, since I'm not sure I did that one.

It was odd that it failed twice pretty close together like that. In ~100 factorizations, that's only twice that I've ever seen that...

Later,
Frank

[jasonp]

Originally Posted by schickel

Jason,
Cool. I updated to 1.18 on one of my PCs, although I'll have to check the other one now, since I'm not sure I did that one.

It was odd that it failed twice pretty close together like that. In ~100 factorizations, that's only twice that I've ever seen that...

There's nothing preventing it from happening during any factorization, it just amounts to a (randomly) bad choice of starting solution to the linear algebra. Linear algebra failure is more likely at the smaller problem sizes; I've seen 40-digit factorizations have three failures in a row before the linear algebra succeeds. I suppose it also is more likely now that QS finds fewer dependencies by default, in order to make the linear algebra complete faster.

I actually just received a report that factorizations also fail after a linear algebra restart when using the latest version too; the next version will include structural changes to the linear algebra that will hopefully remove the possibility of these kinds of problems in the future. For now, restarting msieve should allow the factors to get found.

jasonp

[jasong]

Originally Posted by schickel

Jason, what are the odds of this happening:

I knew this wasn't aimed at me a split second after I read it, but the experience is still rather peculiar. Kind of makes me wonder why anyone would even want to show up at a John Smith convention when their name is John Smith.(Yes, there ARE conventions of this sort. They're probably even more popular now that communication over the Internet is possible.)

Carry on.