20130424, 16:08  #1 
Mar 2006
13·41 Posts 
Advice for large GNFS jobs?
Hello everyone, I'm planning on working on a 210digit GNFS number here pretty soon. I'm using msieve (1.51) to do gpu poly selection right now. I see from the msieve.log that it expects to find an E value from 1.16e015 to > 1.34e015. Is this about what others have seen from their large GNFS jobs? Should I look for a poly with larger E? Also, how long would you estimate the sieving to take?
Can I also ask for advice on parameters and which siever to use? I saw that recently Dan Ee posted some optimized binaries for Win64. I plan to use those, but should I use the 15e, or maybe the 16e sievers for this size job? Should I use 2 or 3 large primes on the algebraic side? Should I use 2 or 3 large primes on the rational side? Over what range of values should I sieve for a job this size? What size matrix (dimensions and/or memory size) would we expect from a job this size? I have two large memory machines (48GB and 64GB), hopefully it will fit onto one of those. Will the answer to most of these questions depend on the best poly that I find? I'll ask more when I have a good poly in hand. Thanks for any advice and insights you can provide. 
20130424, 16:19  #2 
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
The builtin parameters for 210digit polynomial selection are not going to work without manual intervention. For example, it's not clear whether you should look for degree5 or degree6. Check Readme.nfs for all the knobs that are necessary to specify how the search should proceed, you will need to override several of them in ways that are not clear to me.
You also should not start with a leading coefficient of 1; Paul Zimmermann has shown that you improve the chances of finding a good polynomial if you look for leading coefficients that balance the optimal skew against the size of the middle polynomial coefficient. That's definitely the case for degree6, and probably true for degree 5. If this is not an RSA challenge number, I hope it has had enough ECM thrown at it... 
20130424, 16:28  #3 
Aug 2005
Seattle, WA
2×13×71 Posts 
Just what would constitute "enough ECM" in this case? The standard rule of thumb would suggest it should be checked to t70, right? I may be wrong, but I doubt it's had that much!

20130424, 16:37  #4 
"Ben"
Feb 2007
2^{2}·3·311 Posts 
Possibly helpful reference, from a number at least twice as easy as your target:
https://listserv.nodak.edu/cgibin/w...;ac63e2ab.1208 
20130425, 13:33  #5  
Mar 2006
13·41 Posts 
Quote:
I am seeing a couple of different reactions from msieve when I run various steps on different computers. (all of these are CUDA enabled and run on computers with Nvidia cards) On my Linux x64 machine, where I built msieve from svn (...maybe 839?), when I run nps it is extremely fast. It can process 500k np1 hits in about 20 minutes, and that's on one core. On my Windows x64 machine, when I run the 32bit CUDAenabled windows msieve (1.51 from sourceforge) it takes about 2.5 hours to process 500k np1 hits on one core. Is this speed difference because of the 32/64 bit difference? Or maybe there is a Linux/Windows speed difference? Or maybe a combination of those two factors? Also, when I run npr on the top ~10000 nps hits, I am seeing similar speed differences. On my Linux x64 machine it takes about 2 hours to process the top 12000 nps hits on 12 cores (1000/core). On my Windows x64 machine with 32bit msieve 1.51, it takes about 25 hours to process the top 16000 nps hits on 16 cores (1000/core). Could this step also be showing a speed difference because of the 32/64 bit difference? As for having enough ECM thrown at it, I don't have the numbers in front of me, but I think I've put in about 1.3*t65 into this. Still a bit off from the recommended t70, but I thought switching now would be a better use of my resources. I only have about 36 cores I can put into sieving, so I may eventually try to open this up as a project here on the forums. But, I'd like to find a good polynomial and good parameters before I get to that point. I'll start looking into tweaking the other poly search parameters like you've mentioned. Thanks for the hints and tips so far. If you or anyone else can think of other things I should consider or try out, I'd be very interested to hear it. 

20130425, 14:08  #6 
Jun 2012
2^{3}·13·37 Posts 
Have you checked Kamada's site? May be helpful on parameter selection (or not).
http://homepage2.nifty.com/m_kamada/math/graphs.htm 
20130605, 13:55  #7 
Mar 2006
13×41 Posts 
I have a few questions about command line options and parameters for msieve 1.51 with CUDA.
1) I know stage1_norm is used in np1. Does it affect nps or npr? 2) I know stage2_norm is used in nps and npr. Does it affect np1? 3) From the documentation, it looks like t X is only used by np1 and not nps or npr. Is this correct? 4) I've read that running np1 multiple times, with a fixed set of arguments, will usually not produce the same results (because the search space is large and is split into pieces and random pieces are searched). I'm wondering if running nps or npr multiple times, with a fixed set of arguments, will always produce the same results? Or could those produce different polynomials because of different random internal states in msieve? 5) Are Murphy E scores directly comparable between degree 5 and degree 6 polynomials? I think not, but I want to be sure. Thanks everyone for the links to help guide me on parameter selection. I have some ideas of what values to use, and I'll be test sieving those probably by the end of this month. BTW, here are some of the best poly's I've found so far for my C210. I'm going to go back and try tweaking the norm's in nps and npr to see if I get anything better. Code:
Degree5 Polynomials: skew 291528643.68, size 1.051e20, alpha 7.678, combined = 9.961e16 rroots = 3 skew 104279094.33, size 1.124e20, alpha 6.911, combined = 1.038e15 rroots = 5 skew 609572156.15, size 9.604e21, alpha 9.019, combined = 9.234e16 rroots = 5 Degree6 Polynomials: skew 1564743.15, size 2.403e15, alpha 10.513, combined = 9.028e016 rroots = 2 
20130605, 17:48  #8  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Quote:
The stage 2 norms don't influence anything in stage 1. Quote:
Quote:
Quote:


20130703, 12:23  #9 
Mar 2006
215_{16} Posts 
I'm starting to do some test sieving on the polynomials I have found for my gnfs C210. I was wondering several different things about this step:
1) Should I try to find the best set of parameters (rlim,alim,lpbr,lpba,mfbr,mfba) using one polynomial, and then use those parameters to compare all the different polynomials I have? Or should I pick one set of parameters, use those to compare my different polynomials, and then try to optimize the parameters based on the winning polynomial? For a gnfs C210: 2) Should I try sieving on the rational or algebraic side? Or does this depend on the winning polynomial? 3) Should I use 2LP or 3LP for the different sides? Or does this also depend on the winning polynomial? 4) When using 2LP that means: mfbr = 2*lpbr and/or mfba = 2*lpba and rlambda/alambda ~= 2.6 (or 2.7), right? 5) When using 3LP that means: mfbr = 3*lpbr and/or mfba = 3*lpba and rlambda/alambda ~= 3.6 (or 3.7), right? I ask 4 and 5 because I sometimes see people quote params of 33bit lpbr/lpba with 64bit mfbr/mfba or a 33bit lpbr/lpba with 96bit mfbr/mfba, instead of 33&66 or 33&99. Right now I'm testing these variables: rlim = {200e6, 350e6, 500e6} alim = {200e6, 350e6, 500e6} lpbr = {32, 33} lpba = {32, 33} mfbr = 64 mfba = 96 at Q=100e6 and Q=500e6. 6) Are these reasonable test points, or should I try some other variations too? 7) Is 16e the right siever to use for a gnfs C210? 8) Does (total yield)*(sec/rel) = total time to find those relations? 9) How many raw relations should I be looking to collect for this gnfs C210? 10) What is a good range of Q to test to find these relations? Q = {50e6 to 500e6}? Or Q = {100e6 to 1000e6}? Or...? Also, down below I am including the results of my test sieving. Do these look like reasonable outputs? I did "f 100000000 c 1000" and "f 500000000 c 1000" for each test to hopefully get a good approximation of how sieving will go over these big ranges. I'm sure there is probably more I should be asking, but these are the big questions I have for right now. I'd appreciate any insights or advice anyone can give on this big project I'm about to undertake. Of the 36 tests suggested above, with results down below, it looks like I probably want to go with t29 or t32. Does this sound right from these results? Code:
*** Test *** rlim alim lpbr lpba mfbr mfba *** t01 *** 200e6 200e6 32 32 64 96 total yield: 586, q=100001029 (2.49877 sec/rel) total yield: 434, q=500001001 (3.45742 sec/rel) *** t02 *** 350e6 200e6 32 32 64 96 total yield: 640, q=100001029 (2.51675 sec/rel) total yield: 468, q=500001001 (3.50973 sec/rel) *** t03 *** 500e6 200e6 32 32 64 96 total yield: 665, q=100001029 (2.61559 sec/rel) total yield: 480, q=500001001 (3.67786 sec/rel) *** t04 *** 200e6 350e6 32 32 64 96 total yield: 586, q=100001029 (2.49873 sec/rel) total yield: 457, q=500001001 (3.63930 sec/rel) *** t05 *** 350e6 350e6 32 32 64 96 total yield: 640, q=100001029 (2.51599 sec/rel) total yield: 492, q=500001001 (3.65579 sec/rel) *** t06 *** 500e6 350e6 32 32 64 96 total yield: 665, q=100001029 (2.61557 sec/rel) total yield: 505, q=500001001 (3.81100 sec/rel) *** t07 *** 200e6 500e6 32 32 64 96 total yield: 586, q=100001029 (2.50044 sec/rel) total yield: 469, q=500001001 (3.81422 sec/rel) *** t08 *** 350e6 500e6 32 32 64 96 total yield: 640, q=100001029 (2.51385 sec/rel) total yield: 505, q=500001001 (3.82250 sec/rel) *** t09 *** 500e6 500e6 32 32 64 96 total yield: 665, q=100001029 (2.61408 sec/rel) total yield: 519, q=500001001 (3.96526 sec/rel) *** t10 *** 200e6 200e6 32 33 64 96 total yield: 897, q=100001029 (1.63303 sec/rel) total yield: 703, q=500001001 (2.14675 sec/rel) *** t11 *** 350e6 200e6 32 33 64 96 total yield: 993, q=100001029 (1.62162 sec/rel) total yield: 748, q=500001001 (2.19623 sec/rel) *** t12 *** 500e6 200e6 32 33 64 96 total yield: 1029, q=100001029 (1.69091 sec/rel) total yield: 771, q=500001001 (2.29173 sec/rel) *** t13 *** 200e6 350e6 32 33 64 96 total yield: 897, q=100001029 (1.63289 sec/rel) total yield: 761, q=500001001 (2.18615 sec/rel) *** t14 *** 350e6 350e6 32 33 64 96 total yield: 993, q=100001029 (1.62174 sec/rel) total yield: 808, q=500001001 (2.22832 sec/rel) *** t15 *** 500e6 350e6 32 33 64 96 total yield: 1029, q=100001029 (1.69071 sec/rel) total yield: 833, q=500001001 (2.31128 sec/rel) *** t16 *** 200e6 500e6 32 33 64 96 total yield: 897, q=100001029 (1.63459 sec/rel) total yield: 784, q=500001001 (2.28254 sec/rel) *** t17 *** 350e6 500e6 32 33 64 96 total yield: 993, q=100001029 (1.62053 sec/rel) total yield: 836, q=500001001 (2.31623 sec/rel) *** t18 *** 500e6 500e6 32 33 64 96 total yield: 1029, q=100001029 (1.68960 sec/rel) total yield: 862, q=500001001 (2.39455 sec/rel) *** t19 *** 200e6 200e6 33 32 64 96 total yield: 783, q=100001029 (1.89119 sec/rel) total yield: 589, q=500001001 (2.57094 sec/rel) *** t20 *** 350e6 200e6 33 32 64 96 total yield: 861, q=100001029 (1.89129 sec/rel) total yield: 644, q=500001001 (2.57473 sec/rel) *** t21 *** 500e6 200e6 33 32 64 96 total yield: 900, q=100001029 (1.95379 sec/rel) total yield: 663, q=500001001 (2.68922 sec/rel) *** t22 *** 200e6 350e6 33 32 64 96 total yield: 783, q=100001029 (1.89126 sec/rel) total yield: 621, q=500001001 (2.70439 sec/rel) *** t23 *** 350e6 350e6 33 32 64 96 total yield: 861, q=100001029 (1.89104 sec/rel) total yield: 680, q=500001001 (2.67079 sec/rel) *** t24 *** 500e6 350e6 33 32 64 96 total yield: 900, q=100001029 (1.95429 sec/rel) total yield: 702, q=500001001 (2.76947 sec/rel) *** t25 *** 200e6 500e6 33 32 64 96 total yield: 783, q=100001029 (1.89111 sec/rel) total yield: 638, q=500001001 (2.83263 sec/rel) *** t26 *** 350e6 500e6 33 32 64 96 total yield: 861, q=100001029 (1.89246 sec/rel) total yield: 698, q=500001001 (2.79481 sec/rel) *** t27 *** 500e6 500e6 33 32 64 96 total yield: 900, q=100001029 (1.95448 sec/rel) total yield: 721, q=500001001 (2.88571 sec/rel) *** t28 *** 200e6 200e6 33 33 64 96 total yield: 1183, q=100001029 (1.25192 sec/rel) total yield: 945, q=500001001 (1.60321 sec/rel) *** t29 *** 350e6 200e6 33 33 64 96 total yield: 1310, q=100001029 (1.24225 sec/rel) total yield: 1023, q=500001001 (1.62118 sec/rel) *** t30 *** 500e6 200e6 33 33 64 96 total yield: 1372, q=100001029 (1.28140 sec/rel) total yield: 1056, q=500001001 (1.68797 sec/rel) *** t31 *** 200e6 350e6 33 33 64 96 total yield: 1183, q=100001029 (1.25142 sec/rel) total yield: 1017, q=500001001 (1.65128 sec/rel) *** t32 *** 350e6 350e6 33 33 64 96 total yield: 1310, q=100001029 (1.24304 sec/rel) total yield: 1102, q=500001001 (1.64791 sec/rel) *** t33 *** 500e6 350e6 33 33 64 96 total yield: 1372, q=100001029 (1.28214 sec/rel) total yield: 1141, q=500001001 (1.70360 sec/rel) *** t34 *** 200e6 500e6 33 33 64 96 total yield: 1183, q=100001029 (1.25128 sec/rel) total yield: 1048, q=500001001 (1.72428 sec/rel) *** t35 *** 350e6 500e6 33 33 64 96 total yield: 1310, q=100001029 (1.24330 sec/rel) total yield: 1138, q=500001001 (1.71471 sec/rel) *** t36 *** 500e6 500e6 33 33 64 96 total yield: 1372, q=100001029 (1.28211 sec/rel) total yield: 1178, q=500001001 (1.76656 sec/rel) 
20130703, 15:29  #10 
"Curtis"
Feb 2005
Riverside, CA
2·3^{2}·313 Posts 
t13 looks stronger than t29 or t32.
Do these parameter choices change for a sextic vs a quintic? Did you ever figure out if the stage 2 speed differences were 32 vs 64 bitness, or win vs linux? 
20130703, 15:45  #11 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
1011110001111_{2} Posts 
They should I would imagine as with a sextic the algebraic side is harder to factor than the quintic.
The 96 bit limit is a limitation of that version of the siever. If you use lasieve5(only available for linux and a bit buggy) then this limit can be passed. Last fiddled with by henryzz on 20130703 at 15:47 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Advice for large SNFS jobs?  ryanp  Factoring  69  20130430 00:28 
doing large NFS jobs on Amazon EC2?  ixfd64  Factoring  3  20120606 08:27 
Seeking GNFS factoring advice...  WraithX  Msieve  18  20120520 22:19 
need some advice: gnfs C164 from 162126:i4274  Syd  Aliquot Sequences  7  20110314 18:35 
Filtering on large NFS jobs, particularly 2^908+1  bdodson  Factoring  20  20081126 20:45 