mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2015-05-26, 22:56   #1
eigma
 
May 2015

5 Posts
Default "lanczos error: only trivial dependencies found" with massive oversieving

Hi,

I'm trying to factor this number:
0x8BF71731E9F20613EAF148B968500DD365AD4E82785834AD8B213EFFE18A266E85BE6

I have built msieve from SVN, and sieved in client mode (-c) on a cluster for some time, and collected about 80 MB of msieve.dat, containing about 2.8 M relations. I know this is way too much than is needed for my (83 digit) number (msieve suggests 20721).

I hoped that even though I oversieved, msieve will be able to postprocess it. But I get an error:

Msieve v. 1.53 (SVN unknown)
random seeds: 1f44e789 8e14c083
factoring 66383309453566912535245171885971479364236928003151725002082639104940374547086466022 (83 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (74-digit input)
using multiplier of 53
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 496913 (20625 primes)
using large prime bound of 49691300 (25 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 9 factors
restarting with 239120 full and 2603134 partial relations

1860237 relations (239120 full + 1621117 combined from 2603134 partial), need 20721
sieving complete, commencing postprocessing
begin with 2842254 relations
reduce to 2406456 relations in 2 passes
attempting to read 2406456 relations
recovered 2406456 relations
recovered 1157709 polynomials
attempting to build 1860237 cycles
found 1860237 cycles in 1 passes
distribution of cycle lengths:
length 1 : 239120
length 2 : 1621117
largest cycle: 2 relations
matrix is 20625 x 1860237 (303.7 MB) with weight 64744327 (34.80/col)
sparse part has weight 64744327 (34.80/col)
filtering completed in 1 passes
matrix is 20625 x 20689 (2.1 MB) with weight 392902 (18.99/col)
sparse part has weight 392902 (18.99/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 20577 x 20689 (1.8 MB) with weight 323181 (15.62/col)
sparse part has weight 263480 (12.74/col)
commencing Lanczos iteration
memory use: 1.8 MB
lanczos halted after 319 iterations (dim = 20075)
lanczos error: only trivial dependencies found
p1 factor: 2
p1 factor: 7
p2 factor: 47
p4 factor: 2579
p4 factor: 3373
c74 factor: 11597525146521041634094687650227608247344646546873962703205024876012114077
elapsed time 00:00:50

Actually msieve crashes sometimes, though that's a minor issue and I managed to quick fix it for now.

I noticed that if I only feed about 8 MB of msieve.dat (280K relations), msieve succeeds and finds the factorization:

Msieve v. 1.53 (SVN unknown)
random seeds: b1e5fe37 aa1f5186
factoring 66383309453566912535245171885971479364236928003151725002082639104940374547086466022 (83 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (74-digit input)
using multiplier of 53
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 496913 (20625 primes)
using large prime bound of 49691300 (25 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 9 factors
restarting with 24058 full and 261548 partial relations

71100 relations (24058 full + 47042 combined from 261548 partial), need 20721
sieving complete, commencing postprocessing
begin with 285606 relations
reduce to 106829 relations in 2 passes
attempting to read 106829 relations
recovered 106829 relations
recovered 75058 polynomials
attempting to build 71100 cycles
found 71100 cycles in 1 passes
distribution of cycle lengths:
length 1 : 24058
length 2 : 47042
largest cycle: 2 relations
matrix is 20625 x 71100 (10.8 MB) with weight 2259487 (31.78/col)
sparse part has weight 2259487 (31.78/col)
filtering completed in 4 passes
matrix is 12827 x 12891 (1.7 MB) with weight 331569 (25.72/col)
sparse part has weight 331569 (25.72/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 12779 x 12891 (1.3 MB) with weight 251555 (19.51/col)
sparse part has weight 201080 (15.60/col)
commencing Lanczos iteration
memory use: 1.3 MB
lanczos halted after 204 iterations (dim = 12778)
recovered 17 nontrivial dependencies
p1 factor: 2
p1 factor: 7
p2 factor: 47
p4 factor: 2579
p4 factor: 3373
p16 factor: 7771327650084107
p58 factor: 1492347983345615947908133551632827996734568807242686302711
elapsed time 00:00:06

I can do some trial and error, but I want to build a system that can automatically factor many such numbers, and numbers much larger than the example I gave above, so I want to avoid manual work if possible.

How can I reliably determine when I need to stop sieving?
eigma is offline   Reply With Quote
Old 2015-05-27, 00:21   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
Originally Posted by eigma View Post
Hi,

I'm trying to factor this number:
0x8BF71731E9F20613EAF148B968500DD365AD4E82785834AD8B213EFFE18A266E85BE6

I have built msieve from SVN, and sieved in client mode (-c) on a cluster for some time, and collected about 80 MB of msieve.dat, containing about 2.8 M relations. I know this is way too much than is needed for my (83 digit) number (msieve suggests 20721).
Massive doesn't even begin to describe it. This number could have been factored in 5 minutes with a single thread. If you want to factor much larger numbers you will be using NFS instead of QS. In which case you should probably be starting here.
bsquared is offline   Reply With Quote
Old 2015-05-27, 01:06   #3
eigma
 
May 2015

516 Posts
Default

This was only a small scale test, I was hoping to find that msieve reliably factors after a certain number of relations.

The numbers I am actually trying to factor are 154 digits. What would be the performance difference between QS and NFS in this range?

Is NFS as easy to parallelize as QS? (Concatenate msieve.dat from independent runs and retry post processing occasionally?)
eigma is offline   Reply With Quote
Old 2015-05-27, 04:06   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by eigma View Post
This was only a small scale test, I was hoping to find that msieve reliably factors after a certain number of relations.

The numbers I am actually trying to factor are 154 digits. What would be the performance difference between QS and NFS in this range?

Is NFS as easy to parallelize as QS? (Concatenate msieve.dat from independent runs and retry post processing occasionally?)
Whatever Msieve suggests, with at the *very most* a 50% smudge factor, is sufficient. Going ten times past that number, it wouldn't be a surprise for the code to fail (though you seemed to be succesful with it). A hundred times past that number... was seriously just several dollars of energy converted to heat for literally no purpose.

Although I am not sufficiently familiar with the QS time growth rate in practice to make a reasonable prediction, I suspect a 150+ QS job would take a year or more, if even within the century (and that's assuming any currently written QS implementation will successfully go that high, which I also rather doubt). With NFS it'll take a month or possibly less on new hardware.
Dubslow is offline   Reply With Quote
Old 2015-05-27, 05:20   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,789 Posts
Red face

Quote:
Originally Posted by eigma View Post
This was only a small scale test, I was hoping to find that msieve reliably factors after a certain number of relations.

The numbers I am actually trying to factor are 154 digits. What would be the performance difference between QS and NFS in this range?

Is NFS as easy to parallelize as QS? (Concatenate msieve.dat from independent runs and retry post processing occasionally?)
1. msieve on a C154 will build and solve a matrix after 85M relations reliably, if you use 31-bit large primes and reasonably good polynomial selection (say, a CPU week or a GPU day, though 2-3 GPU days is probly useful). A little experimentation on your desired size of candidate will help quite a bit. I've factored a GNFS-155 and a GNFS-156 with 80-81M relations, but I use the factmsieve.py script to manage the process; if a matrix fails to build, it calls the sieve step for a few more hours and then tries again. That's likely as automated as you need it to be; you can tweak lots of the parameters within the script to eke out small gains at 150+ digits, or just use it as supplied to do what you're looking for.

2. A month vs over a century might be right, if using a single machine. A 150-digit QS job would set a record for that method, I believe.

3. Yes.
VBCurtis is online now   Reply With Quote
Old 2015-05-27, 05:56   #6
eigma
 
May 2015

5 Posts
Default

Thanks. I will focus my efforts on GNFS.

Are these the correct places to get the latest msieve, ggnfs and factmsieve.74.py?
http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/
http://sourceforge.net/p/ggnfs/code/HEAD/tree/trunk/
https://github.com/GDSSecurity/cloud...ctmsieve.74.py

I have checked "Beginners Guide to NFS factoring using GGNFS and MSIEVE" as linked by bsquared but there are some broken links.
eigma is offline   Reply With Quote
Old 2015-05-27, 06:17   #7
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

For factoring 512-bit RSA keys, 85M raw relations represents significant oversieving. IME, 70M raw relations do the job.
debrouxl is offline   Reply With Quote
Old 2015-05-27, 06:43   #8
eigma
 
May 2015

5 Posts
Default

The numbers are indeed 512 bit, but they are not RSA keys. They are products of two random 256 bit numbers.
eigma is offline   Reply With Quote
Old 2015-05-27, 07:16   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,143 Posts
Default

Quote:
Originally Posted by eigma View Post
The numbers are indeed 512 bit, but they are not RSA keys. They are products of two random 256 bit numbers.
That last sentence appears to be describing RSA modulus numbers perfectly reasonably. If it looks like a duck ...
retina is offline   Reply With Quote
Old 2015-05-27, 10:05   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

The NFS postprocessing is designed to run in Msieve conceptually in the same way as it does in QS; concatenate relation files from multiple sieving machines and run the postprocessing on the one result. But the sieving in Msieve is not competitive with the performance of other NFS sieve codes, so you should be using those codes instead in your pipeline. Parameter selection is also not very well understood, so some guesswork is usually required. Guesswork requires familiarity with the algorithm.

The record for QS is 136 digits.
jasonp is offline   Reply With Quote
Old 2015-05-27, 10:38   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by jasonp View Post
The NFS postprocessing is designed to run in Msieve conceptually in the same way as it does in QS; concatenate relation files from multiple sieving machines and run the postprocessing on the one result. But the sieving in Msieve is not competitive with the performance of other NFS sieve codes, so you should be using those codes instead in your pipeline. Parameter selection is also not very well understood, so some guesswork is usually required. Guesswork requires familiarity with the algorithm.

The record for QS is 136 digits.
Morons. Morons. Morons. I am surrounded by morons.

Did anyone happen to notice that the number trying to be factored is even? That it is 2 mod 4?
That there are no squares that are 2 mod 4?

Why let two seconds of thought get in the way of massive blind computing?

Last fiddled with by R.D. Silverman on 2015-05-27 at 10:39
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"error: unexpected dense ideal found" fivemack Msieve 13 2016-08-15 04:30
mfaktX result: "found 1 factor for M" swl551 GPU Computing 2 2012-12-20 15:20
v1.40 patch for massive NFS oversieving jasonp Msieve 18 2009-04-09 03:20
"Trivial" factorization algorithms Fusion_power Math 13 2004-12-28 20:46
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

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

Mon May 17 19:12:31 UTC 2021 up 39 days, 13:53, 0 users, load averages: 3.16, 2.91, 2.85

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.