"lanczos error: only trivial dependencies found" with massive oversieving

eigma · 2015-05-26, 22:56

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?

bsquared · 2015-05-27, 00:21

Quote:

Originally Posted by eigma

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.

eigma · 2015-05-27, 01:06

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?)

Dubslow · 2015-05-27, 04:06

Quote:

Originally Posted by eigma

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.

VBCurtis · 2015-05-27, 05:20

Quote:

Originally Posted by eigma

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.

eigma · 2015-05-27, 05:56

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.

debrouxl · 2015-05-27, 06:17

For factoring 512-bit RSA keys, 85M raw relations represents significant oversieving. IME, 70M raw relations do the job.

eigma · 2015-05-27, 06:43

The numbers are indeed 512 bit, but they are not RSA keys. They are products of two random 256 bit numbers.

retina · 2015-05-27, 07:16

Quote:

Originally Posted by eigma

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 ...

jasonp · 2015-05-27, 10:05

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.

R.D. Silverman · 2015-05-27, 10:38

Quote:

Originally Posted by jasonp

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?

2015-05-26, 22:56	#1
eigma May 2015 5 Posts	"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?

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

2015-05-27, 01:06	#3
eigma May 2015 5 Posts	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?)

2015-05-27, 05:56	#6
eigma May 2015 5₁₀ Posts	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.

2015-05-27, 06:17	#7
debrouxl Sep 2009 1111010001₂ Posts	For factoring 512-bit RSA keys, 85M raw relations represents significant oversieving. IME, 70M raw relations do the job.

2015-05-27, 06:43	#8
eigma May 2015 5₁₀ Posts	The numbers are indeed 512 bit, but they are not RSA keys. They are products of two random 256 bit numbers.

2015-05-27, 10:05	#10
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	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.