20150526, 22:56  #1 
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 P1/P+1/ECM available, skipping commencing quadratic sieve (74digit 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 P1/P+1/ECM available, skipping commencing quadratic sieve (74digit 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? 
20150527, 00:21  #2  
"Ben"
Feb 2007
41×83 Posts 
Quote:


20150527, 01:06  #3 
May 2015
5_{8} 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?) 
20150527, 04:06  #4  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
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. 

20150527, 05:20  #5  
"Curtis"
Feb 2005
Riverside, CA
127B_{16} Posts 
Quote:
2. A month vs over a century might be right, if using a single machine. A 150digit QS job would set a record for that method, I believe. 3. Yes. 

20150527, 05:56  #6 
May 2015
101_{2} 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. 
20150527, 06:17  #7 
Sep 2009
977 Posts 
For factoring 512bit RSA keys, 85M raw relations represents significant oversieving. IME, 70M raw relations do the job.

20150527, 06:43  #8 
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.

20150527, 07:16  #9 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5·1,223 Posts 

20150527, 10:05  #10 
Tribal Bullet
Oct 2004
2^{4}·13·17 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. 
20150527, 10:38  #11  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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 20150527 at 10:39 

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