mersenneforum.org Choosing the best polynomial
 Register FAQ Search Today's Posts Mark Forums Read

 2013-06-15, 15:12 #1 wombatman I moo ablest echo power!     May 2013 22·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!
 2013-06-15, 20:37 #2 WraithX     Mar 2006 21616 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 .ms | head -100 > top_nps.ms For degree 6 polynomials: sort -g -k 11 .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/
 2013-06-15, 20:39 #3 wombatman I moo ablest echo power!     May 2013 22·463 Posts Wonderful advice, Wraith. I was stuck at the '-npr' step, so this will be very helpful. Thanks!
 2013-06-15, 21:02 #4 jasonp Tribal Bullet     Oct 2004 32×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.
 2013-06-15, 21:13 #5 wombatman I moo ablest echo power!     May 2013 22·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 And I've tried swapping out 'top_nps.ms' in a few places. I've also looked the readme.nfs, and it was very helpful, but I didn't see an answer to this. Thanks again! 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 2013-06-15 at 21:28
 2013-06-15, 23:23 #6 jasonp Tribal Bullet     Oct 2004 32·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.
 2013-06-16, 00:22 #7 wombatman I moo ablest echo power!     May 2013 73C16 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 P-1/P+1/ECM available, skipping commencing number field sieve (210-digit input) R0: -18956134228085985405529211909369637937232 R1: 34148699207296727339 A0: -68745161487875013342557283048324779969899385250015 A1: -1153486306530874249203975970223434209448064 A2: 45812802297679867731685253504866941 A3: -184320364928426528174017362 A4: -1285982601893320700 A5: 100196880 skew 220770312.64, size 7.160e-021, alpha -7.766, combined = 7.536e-016 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) Apologies if this is a dumb question, but is this simply a matter of running out of memory? Or is it a different sort of error?
 2013-06-16, 02:29 #8 jasonp Tribal Bullet     Oct 2004 32·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 5-10x 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 machine-years 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 204-digit GNFS job, plus hundreds of cores crunching for NFS@Home to do the sieving. Last fiddled with by jasonp on 2013-06-16 at 02:34
 2013-06-16, 03:41 #9 wombatman I moo ablest echo power!     May 2013 22×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!
 2013-06-16, 22:32 #10 wombatman I moo ablest echo power!     May 2013 22·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 E-score, but is there a good way to know approximately where that score should be for a number X digits in length? Thanks.
2013-06-17, 03:23   #11
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

23×3×5×47 Posts

Quote:
 Originally Posted by wombatman 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 E-score, but is there a good way to know approximately where that score should be for a number X digits in length? Thanks.
Sure- lots of experience. Luckily, msieve has the results of that experience coded right in. Check the log file when you start a poly search, as it tells you what a "good" poly is expected to be. There is no guarantee the actual poly you find will fall into that range, but it is exactly the approximation you seek.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 14 2017-02-18 19:46 Flatlander GPU Computing 4 2011-01-26 08:15 siew Factoring 14 2010-02-27 10:07 ThiloHarich Factoring 4 2006-09-05 07:51 azhad Software 2 2004-10-16 16:41

All times are UTC. The time now is 09:51.

Mon Feb 6 09:51:19 UTC 2023 up 172 days, 7:19, 1 user, load averages: 1.21, 0.98, 0.90