Choosing the best polynomial

[wombatman]

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!

[WraithX]

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/

[wombatman]

Wonderful advice, Wraith. I was stuck at the '-npr' step, so this will be very helpful. Thanks!

[jasonp]

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.

[wombatman]

Sorry guys, one last stupid question. How do I specify for msieve to pull from the top_nps.ms file? I'm using this:

$ 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!

[jasonp]

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.

[wombatman]

So the root optimization works, and I can generate a factor base file. Next up, I did '-ns', and I get the following output:

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?

[jasonp]

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.

[wombatman]

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!

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

[VBCurtis]

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.