mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2013-06-15, 15:12   #1
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×349 Posts
Default 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!
wombatman is offline   Reply With Quote
Old 2013-06-15, 20:37   #2
WraithX
 
WraithX's Avatar
 
Mar 2006

11×43 Posts
Default

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/
WraithX is offline   Reply With Quote
Old 2013-06-15, 20:39   #3
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×349 Posts
Default

Wonderful advice, Wraith. I was stuck at the '-npr' step, so this will be very helpful. Thanks!
wombatman is offline   Reply With Quote
Old 2013-06-15, 21:02   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353710 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2013-06-15, 21:13   #5
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×349 Posts
Default

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
wombatman is offline   Reply With Quote
Old 2013-06-15, 23:23   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67218 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2013-06-16, 00:22   #7
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

174510 Posts
Default

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?
wombatman is offline   Reply With Quote
Old 2013-06-16, 02:29   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2013-06-16, 03:41   #9
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·349 Posts
Default

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 offline   Reply With Quote
Old 2013-06-16, 22:32   #10
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·349 Posts
Default

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.
wombatman is offline   Reply With Quote
Old 2013-06-17, 03:23   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

13×367 Posts
Default

Quote:
Originally Posted by wombatman View Post
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.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
Help choosing motherboard please. Flatlander GPU Computing 4 2011-01-26 08:15
Choosing the best CPU for sieving siew Factoring 14 2010-02-27 10:07
MPQS: choosing a good polynomial ThiloHarich Factoring 4 2006-09-05 07:51
Choosing amount of memory azhad Software 2 2004-10-16 16:41

All times are UTC. The time now is 19:58.

Fri May 7 19:58:46 UTC 2021 up 29 days, 14:39, 1 user, load averages: 2.09, 2.16, 2.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.