20090124, 08:50  #1 
"Frank <^>"
Dec 2004
CDP Janesville
2×1,061 Posts 
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 Last fiddled with by schickel on 20090124 at 09:00 Reason: Adding note.... 
20090124, 08:54  #2  
Nov 2008
2×3^{3}×43 Posts 
Quote:
I'll run that one here to see if I get the same thing. Last fiddled with by 10metreh on 20090124 at 08:55 

20090124, 09:42  #3 
Nov 2008
2×3^{3}×43 Posts 
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 15digit factors Sat Jan 24 08:57:57 2009 commencing quadratic sieve (83digit 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 Last fiddled with by 10metreh on 20090124 at 09:42 
20090124, 09:46  #4 
Oct 2004
Austria
2482_{10} Posts 
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 15digit factors Sat Jan 24 10:08:49 2009 commencing quadratic sieve (83digit 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 
20090124, 11:13  #5 
"Frank <^>"
Dec 2004
CDP Janesville
2·1,061 Posts 
Second time through did it. Guess it's just one of those little "wobblies" that makes life interesting....

20090124, 11:39  #6 
Nov 2008
2·3^{3}·43 Posts 
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.

20090124, 13:11  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Which kernel vectors BlockLanczos 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 
20090124, 14:41  #8 
Tribal Bullet
Oct 2004
2^{4}·13·17 Posts 
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. 
20090124, 15:50  #9  
Nov 2008
2·3^{3}·43 Posts 
Quote:


20090124, 18:02  #10 
Tribal Bullet
Oct 2004
2^{4}×13×17 Posts 
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 1016 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. Last fiddled with by jasonp on 20090124 at 18:07 
20090204, 11:51  #11  
"Frank <^>"
Dec 2004
CDP Janesville
100001001010_{2} Posts 
Ooops, I did it again!
Quote:
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 recovered 1 nontrivial dependencies c81 factor: 209612803501572769613503479346205323106543199395228972781161784934907857678327057 Code:
prp32 factor: 14202981758988057504195921169853 prp50 factor: 14758366028944853574664033531885329816029769322469 Shoot.....only a 1/32768 chance. Not quite enough to go play the lottery yet! (Or am I off by a factor of 2?) Last fiddled with by schickel on 20090204 at 12:02 Reason: Finished counting on fingers and toes.... And adjusting tags 
