Here's an odd one

schickel · 2009-01-24, 08:50

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

I'll throw it back in the mixer for one more round....

10metreh · 2009-01-24, 08:54

Quote:

Originally Posted by schickel

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

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.

10metreh · 2009-01-24, 09:42

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

Andi47 · 2009-01-24, 09:46

Quote:

Originally Posted by 10metreh

It finished fine for me:

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

schickel · 2009-01-24, 11:13

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

10metreh · 2009-01-24, 11:39

Quote:

Originally Posted by schickel

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

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.

akruppa · 2009-01-24, 13:11

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

jasonp · 2009-01-24, 14:41

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.

10metreh · 2009-01-24, 15:50

Quote:

Originally Posted by jasonp

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.

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

jasonp · 2009-01-24, 18:02

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.

schickel · 2009-02-04, 11:51

Quote:

Originally Posted by 10metreh

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

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
recovered 1 nontrivial dependencies
c81 factor: 209612803501572769613503479346205323106543199395228972781161784934907857678327057

BTW, for those of you following along at home:

Code:

prp32 factor: 14202981758988057504195921169853
prp50 factor: 14758366028944853574664033531885329816029769322469

Maybe there's something special about my small numbers!

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

2009-01-24, 18:02	#10
jasonp Tribal Bullet Oct 2004 3,541 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 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. Last fiddled with by jasonp on 2009-01-24 at 18:07

2009-01-24, 11:13	#5
schickel "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....

2009-01-24, 13:11	#7
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	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

2009-01-24, 14:41	#8
jasonp Tribal Bullet Oct 2004 3541₁₀ 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.