Here's an odd one
 

I batch factor my aliquot composites overnight, so I don't have anything but the log on this one:[code]factoring 55213655784106271888811487247969833626739949447886509091046186980242042559027585931 (83 digits)
. . . . .
matrix is 44650 x 44762 with weight 1045028 (avg 23.35/col)
matrix includes 64 packed rows
commencing Lanczos iteration
lanczos halted after 707 iterations
recovered 3 nontrivial dependencies
c83 factor: 55213655784106271888811487247969833626739949447886509091046186980242042559027585931
elapsed time 00:25:26[/code]I'll throw it back in the mixer for one more round....

[quote=schickel;160165]I batch factor my aliquot composites overnight, so I don't have anything but the log on this one:[code]factoring 55213655784106271888811487247969833626739949447886509091046186980242042559027585931 (83 digits)
. . . . .
matrix is 44650 x 44762 with weight 1045028 (avg 23.35/col)
matrix includes 64 packed rows
commencing Lanczos iteration
lanczos halted after 707 iterations
recovered 3 nontrivial dependencies
c83 factor: 55213655784106271888811487247969833626739949447886509091046186980242042559027585931
elapsed time 00:25:26[/code][/quote]

Only 3 nontrivial dependencies? I've never seen anything that low. Could the sqrt have failed on all of them?

I'll run that one here to see if I get the same thing.

It finished fine for me:

[code]Sat Jan 24 08:57:53 2009 Msieve v. 1.39
Sat Jan 24 08:57:53 2009 random seeds: ad65909c 0341a8b4
Sat Jan 24 08:57:53 2009 factoring 55213655784106271888811487247969833626739949447886509091046186980242042559027585931 (83 digits)
Sat Jan 24 08:57:55 2009 searching for 15-digit factors
Sat Jan 24 08:57:57 2009 commencing quadratic sieve (83-digit input)
...
Sat Jan 24 09:38:34 2009 commencing Lanczos iteration
Sat Jan 24 09:38:34 2009 memory use: 4.1 MB
Sat Jan 24 09:38:51 2009 lanczos halted after 586 iterations (dim = 36986)
Sat Jan 24 09:38:51 2009 recovered 16 nontrivial dependencies
Sat Jan 24 09:38:52 2009 prp30 factor: 569867820812119023553920654323
Sat Jan 24 09:38:52 2009 prp53 factor: 96888530581392107804011724020890396778892480736524297
Sat Jan 24 09:38:52 2009 elapsed time 00:40:59[/code]

[QUOTE=10metreh;160173]It finished fine for me:
[/quote]

for me too:

[code]Sat Jan 24 10:08:46 2009
Sat Jan 24 10:08:46 2009
Sat Jan 24 10:08:46 2009 Msieve v. 1.39
Sat Jan 24 10:08:46 2009 random seeds: cdb91e68 664cc86b
Sat Jan 24 10:08:46 2009 factoring 55213655784106271888811487247969833626739949447886509091046186980242042559027585931 (83 digits)
Sat Jan 24 10:08:47 2009 searching for 15-digit factors
Sat Jan 24 10:08:49 2009 commencing quadratic sieve (83-digit input)
Sat Jan 24 10:08:49 2009 using multiplier of 1
Sat Jan 24 10:08:49 2009 using 64kb Pentium 4 sieve core
Sat Jan 24 10:08:49 2009 sieve interval: 6 blocks of size 65536
Sat Jan 24 10:08:49 2009 processing polynomials in batches of 17
Sat Jan 24 10:08:49 2009 using a sieve bound of 1365307 (52647 primes)
Sat Jan 24 10:08:49 2009 using large prime bound of 121512323 (26 bits)
Sat Jan 24 10:08:49 2009 using trial factoring cutoff of 27 bits
Sat Jan 24 10:08:49 2009 polynomial 'A' values have 11 factors
Sat Jan 24 10:45:18 2009 52872 relations (27852 full + 25020 combined from 272007 partial), need 52743
Sat Jan 24 10:45:18 2009 begin with 299859 relations
Sat Jan 24 10:45:18 2009 reduce to 74737 relations in 2 passes
Sat Jan 24 10:45:18 2009 attempting to read 74737 relations
Sat Jan 24 10:45:19 2009 recovered 74737 relations
Sat Jan 24 10:45:19 2009 recovered 64846 polynomials
Sat Jan 24 10:45:19 2009 attempting to build 52872 cycles
Sat Jan 24 10:45:19 2009 found 52872 cycles in 1 passes
Sat Jan 24 10:45:19 2009 distribution of cycle lengths:
Sat Jan 24 10:45:19 2009 length 1 : 27852
Sat Jan 24 10:45:19 2009 length 2 : 25020
Sat Jan 24 10:45:19 2009 largest cycle: 2 relations
Sat Jan 24 10:45:19 2009 matrix is 52647 x 52872 (7.3 MB) with weight 1714281 (32.42/col)
Sat Jan 24 10:45:19 2009 sparse part has weight 1714281 (32.42/col)
Sat Jan 24 10:45:20 2009 filtering completed in 3 passes
Sat Jan 24 10:45:20 2009 matrix is 37061 x 37122 (5.7 MB) with weight 1336244 (36.00/col)
Sat Jan 24 10:45:20 2009 sparse part has weight 1336244 (36.00/col)
Sat Jan 24 10:45:20 2009 saving the first 48 matrix rows for later
Sat Jan 24 10:45:20 2009 matrix is 37013 x 37122 (3.6 MB) with weight 996094 (26.83/col)
Sat Jan 24 10:45:20 2009 sparse part has weight 714323 (19.24/col)
Sat Jan 24 10:45:20 2009 matrix includes 64 packed rows
Sat Jan 24 10:45:20 2009 using block size 14848 for processor cache size 2048 kB
Sat Jan 24 10:45:21 2009 commencing Lanczos iteration
Sat Jan 24 10:45:21 2009 memory use: 4.1 MB
Sat Jan 24 10:45:33 2009 lanczos halted after 587 iterations (dim = 37010)
Sat Jan 24 10:45:33 2009 recovered 16 nontrivial dependencies
Sat Jan 24 10:45:33 2009 prp30 factor: 569867820812119023553920654323
Sat Jan 24 10:45:33 2009 prp53 factor: 96888530581392107804011724020890396778892480736524297
Sat Jan 24 10:45:33 2009 elapsed time 00:36:47
[/code]

Second time through did it. Guess it's just one of those little "wobblies" that makes life interesting....

[quote=schickel;160186]Second time through did it. Guess it's just one of those little "wobblies" that makes life interesting....[/quote]

Looking more closely, it seems the error was in the filtering because the matrix was quite a lot larger than it should have been. This gave an unusually low number of dependencies from the linear algebra, and the square root failed on all of them.

Which kernel vectors Block-Lanczos finds depends on the randomly chosen starting vector, and that one presumably is a function of the "random seed" values. So to reproduce BL oddities it may be necessary to make msieve use the same random seed value again. When I looked some time ago, you had to set the value in the source code - there was no command line parameter etc. Dunno what the situation is now.

Alex

That hasn't changed; the random seeds are only printed so that I can reproduce failed runs locally (I can't, by the way). Just using the same random seeds will not automatically produce the same behavior, though, because a later library version might change the way it uses random numbers so that the linear algebra might give itself a different starting vector.

With the current library version matrices from QS factorizations can have at most 16 dependencies, or 15 about 1/2 the time, or 14 about 1/4 the time, etc. So it isn't surprising that once in a great while you'll get 3 dependencies. It's like NFS needing 10 dependencies to split the input once in a great while.

[quote=jasonp;160212]With the current library version matrices from QS factorizations can have at most 16 dependencies, or 15 about 1/2 the time, or 14 about 1/4 the time, etc. So it isn't surprising that once in a great while you'll get 3 dependencies. It's like NFS needing 10 dependencies to split the input once in a great while.[/quote]

Does that mean that one in every 65536 QSs with msieve will fail because there are no dependencies at all?

Larger linear algebra jobs in the past have failed because the only dependency possible was the trivial one, and that can happen even if the matrix is not square (there could be duplicate columns, for example). The odds of that happening are actually the odds that the matrix contains enough duplicate columns to wipe out the nullspace, and I would think the odds of columns being duplicated are fairly small for larger factor bases.

If the input has exactly two factors, you can enumerate the cases where one factor or the other is found, and it turns out the fraction of successful dependencies is 2/3 and not 1/2, so the odds of having 10-16 dependencies fail are lower than your estimate. Even if you did have failures, the QS code would restart, find the old relations, and rerun the linear algebra.

Ooops, I did it again!
 

[QUOTE=10metreh;160166]Only 3 nontrivial dependencies? I've never seen anything that low. Could the sqrt have failed on all of them?[/QUOTE]Obviously you're not living right. (Special note: this already factored for me, no need to waste any time on it.) [code]factoring 209612803501572769613503479346205323106543199395228972781161784934907857678327057 (81 digits)
[. . . .]
matrix is 42204 x 42316 with weight 923155 (avg 21.82/col)
matrix includes 64 packed rows
commencing Lanczos iteration
lanczos halted after 669 iterations
[B]recovered 1 nontrivial dependencies[/B]
c81 factor: 209612803501572769613503479346205323106543199395228972781161784934907857678327057[/code]BTW, for those of you following along at home:[code]prp32 factor: 14202981758988057504195921169853
prp50 factor: 14758366028944853574664033531885329816029769322469[/code]

Maybe there's something special about my small numbers! :grin:

[SIZE="1"]Shoot.....only a 1/32768 chance. Not quite enough to go play the lottery yet! (Or am I off by a factor of 2?)[/SIZE]