mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-01-24, 08:50   #1
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2×1,061 Posts
Exclamation 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
I'll throw it back in the mixer for one more round....

Last fiddled with by schickel on 2009-01-24 at 09:00 Reason: Adding note....
schickel is offline   Reply With Quote
Old 2009-01-24, 08:54   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by schickel View Post
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.

Last fiddled with by 10metreh on 2009-01-24 at 08:55
10metreh is offline   Reply With Quote
Old 2009-01-24, 09:42   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

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

Last fiddled with by 10metreh on 2009-01-24 at 09:42
10metreh is offline   Reply With Quote
Old 2009-01-24, 09:46   #4
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

248210 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
Andi47 is offline   Reply With Quote
Old 2009-01-24, 11:13   #5
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2·1,061 Posts
Talking

Second time through did it. Guess it's just one of those little "wobblies" that makes life interesting....
schickel is offline   Reply With Quote
Old 2009-01-24, 11:39   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by schickel View Post
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.
10metreh is offline   Reply With Quote
Old 2009-01-24, 13:11   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-01-24, 14:41   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-01-24, 15:50   #9
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
10metreh is offline   Reply With Quote
Old 2009-01-24, 18:02   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24×13×17 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-02-04, 11:51   #11
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

1000010010102 Posts
Talking Ooops, I did it again!

Quote:
Originally Posted by 10metreh View Post
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?)

Last fiddled with by schickel on 2009-02-04 at 12:02 Reason: Finished counting on fingers and toes.... And adjusting tags
schickel is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 19:50.

Mon Apr 12 19:50:51 UTC 2021 up 4 days, 14:31, 1 user, load averages: 2.63, 2.64, 2.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.