20130615, 15:12  #1 
I moo ablest echo power!
May 2013
2^{2}·463 Posts 
Choosing the best polynomial
I've been playing around with running msieve directly from the command line (as opposed to using Brian Gladman's python script), but I'm a little confused. I generated potential polynomial factors using the 'np1' flag with no issue. From that 200 MB, I generated the polynomials themselves using the 'npr' flag, resulting in a 300 MB file.
Now I'm using the 'nps' flag to do the optimization step, but I'm wondering if I have to let the full optimization step run, or if I could let it go for a certain amount of time and then generate a .fb file myself. Thanks! 
20130615, 20:37  #2 
Mar 2006
216_{16} Posts 
You can get a very good and detailed explanation of all steps in polynomial selection (and sieving, linear algebra, square root step, etc) from the readme.nfs file. But, here is a short explanation about the polynomial selection steps:
1) The first step is stage 1 polynomial selection, which is run with np1. This will create a .m file. 2) Then you start stage 2 size optimization on all the hits in the np1 file. You run this with the nps option. This will create a .ms file. 3) Then you can run stage 2 root optimization on the top X* hits from the .ms file. You run this with the npr option. This will create a .p file which holds all polynomials found during npr, and when finished will create a .fb file for you with the best polynomial found. Any polynomial from the .p file can be used in your .fb file (if you format the coefficient names correctly). I believe the .fb file can only be used by the msieve siever, and any polynomial from the .p file can be used by the ggnfs sieving tools. * You can probably get away with running npr on the top 100 hits from nps. In order to find the "top 100" from nps you can do the following: For degree 5 polynomials: sort g k 10 <file>.ms  head 100 > top_nps.ms For degree 6 polynomials: sort g k 11 <file>.ms  head 100 > top_nps.ms Where 'sort' and 'head' are unix utilities. They should both be readily available in all Linux distributions, and they are available for windows in the UnixUtils package available here: http://sourceforge.net/projects/unxutils/ 
20130615, 20:39  #3 
I moo ablest echo power!
May 2013
2^{2}·463 Posts 
Wonderful advice, Wraith. I was stuck at the 'npr' step, so this will be very helpful. Thanks!

20130615, 21:02  #4 
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
Root optimization on a single hit takes 100x longer than the size optimization for that hit. So it's a big time saver to find all the best hits from the size optimization and give only those to the root optimization.

20130615, 21:13  #5 
I moo ablest echo power!
May 2013
2^{2}·463 Posts 
Sorry guys, one last stupid question. How do I specify for msieve to pull from the top_nps.ms file? I'm using this:
Code:
$ msieve151_GPU_ZLIB.exe s rsa210.dat i rsa210.ini l rsa210.log v g 0 t 10 nf rsa210.fb npr Edit: And it looks like I got it to work by changing 's rsa210.dat' to 's top_nps' without the .ms. Thanks again for all your help, Wraith and Jason! Last fiddled with by wombatman on 20130615 at 21:28 
20130615, 23:23  #6 
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
You already figured this out, but the name of the file specified in the s argument is a prefix to all the other intermediate files used by the NFS code.

20130616, 00:22  #7 
I moo ablest echo power!
May 2013
73C_{16} Posts 
So the root optimization works, and I can generate a factor base file. Next up, I did 'ns', and I get the following output:
Code:
Msieve v. 1.51 (SVN 1.51 GPU) Sat Jun 15 19:13:10 2013 random seeds: 25befcb8 c6e739d7 factoring 245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067 (210 digits) no P1/P+1/ECM available, skipping commencing number field sieve (210digit input) R0: 18956134228085985405529211909369637937232 R1: 34148699207296727339 A0: 68745161487875013342557283048324779969899385250015 A1: 1153486306530874249203975970223434209448064 A2: 45812802297679867731685253504866941 A3: 184320364928426528174017362 A4: 1285982601893320700 A5: 100196880 skew 220770312.64, size 7.160e021, alpha 7.766, combined = 7.536e016 rroots = 3 generating factor base factor base complete: 1857859 rational roots (max prime = 29999999) 1859254 algebraic roots (max prime = 29999999) a range: [64000000, 64000000] b range: [1, 100] number of hash buckets: 458 sieve block size: 65536 maximum RFB prime: 29999999 RFB entries: 1857859 medium RFB entries: 6542 resieved RFB entries: 6374 small RFB prime powers: 94 projective RFB roots: 5 RFB trial factoring cutoff: 65 or 97 bits single large prime RFB range: 25  29 bits double large prime RFB range: 50  56 bits triple large prime RFB range: 77  85 bits GNU MP: Cannot reallocate memory (old_size=16 new_size=20) 
20130616, 02:29  #8 
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Don't use the line sieve in Msieve; I think a previous round of major changes broke it, and I haven't had a chance to fix it in a while. Even if it worked, using a lattice sieve from elsewhere will finish the sieving 510x faster.
PS: If you're going to try factoring RSA210, you already have an incredibly difficult job ahead of you; just doing the polynomial selection will take several machineyears before you get something good enough to make the sieving barely practical. Greg Childers needed weeks on a supercomputer to do the postprocessing for a 204digit GNFS job, plus hundreds of cores crunching for NFS@Home to do the sieving. Last fiddled with by jasonp on 20130616 at 02:34 
20130616, 03:41  #9 
I moo ablest echo power!
May 2013
2^{2}×463 Posts 
Thanks for the info. I figured I it would take quite a bit of time (I've played around with it previously and see how long each relation step can take), but time is something I have plenty of. I do this just for fun (yes, really!) as something different from my everyday research in solar energy. Thanks again for taking the time to answer all my questions!

20130616, 22:32  #10 
I moo ablest echo power!
May 2013
2^{2}·463 Posts 
Is there a good rule of thumb for determining good 'scores' on a factor base? I know there's the alpha, which you want as negative as possible, and the Murphy Escore, but is there a good way to know approximately where that score should be for a number X digits in length? Thanks.

20130617, 03:23  #11  
"Curtis"
Feb 2005
Riverside, CA
2^{3}×3×5×47 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
Help choosing motherboard please.  Flatlander  GPU Computing  4  20110126 08:15 
Choosing the best CPU for sieving  siew  Factoring  14  20100227 10:07 
MPQS: choosing a good polynomial  ThiloHarich  Factoring  4  20060905 07:51 
Choosing amount of memory  azhad  Software  2  20041016 16:41 