20101120, 01:54  #1 
Nov 2010
2·7 Posts 
A couple of questions about polynomial selection
Hi all,
Sorry if the answers to these questions are very simple, I am new to msieve and still trying to get to grips with it. I am currently trying to factorize a 160 digit key. I ran msieve's polynomial selection for a couple of days and then started sieving with the best key from the limited number generated. My first question is whether if I find a better polynomial (I am still searching as that part runs on my GPU so doesnt slow down the sieving at all), can I continue the sieving with this better one or would I have to disgard all the relations found with the old one and start from scratch again? My second questions is, with msieve's polynomials, what refers to the Murphy score? Is it the 'e' field e.g. 'e 1.075e012', and is the best polynomial the one with the highest value for this, Any help would be much appreciated, Anthony 
20101120, 04:26  #2 
"Serge"
Mar 2008
San Diego, Calif.
10398_{10} Posts 
No.
Yes. 
20101120, 11:56  #3 
Tribal Bullet
Oct 2004
6772_{8} Posts 
This extra credit assignment from Imperial College London really has the class scrambling :)
The Murphy score is the probability that a random value of the NFS polynomials, drawn from somewhere in the sieving region, will have all of its factors smaller than some bound. Larger 'e' score is supposed to be better, since a larger score implies that sieving will find more relations. It's tempting to assume that sieving will run X% faster if using a polynomial whose evalue is X% better, but that doesn't appear to happen when there are large differences in evalue. Once you decide on a polynomial pair, everything else is specific to that pair, so the amount of effort to spend on polynomial selection is a judgment call that depends on how long you anticipate the sieving to take, whether poly selection has gotten lucky yet, and how many machines you have that will be idle until poly selection is done. The cutoff point is particularly tricky when doing poly selection using a graphics card, because most of these individual efforts have several machines but only one graphics card, and I have no idea whether I've chosen the best parameters for that one card to use. 
20101120, 14:34  #4 
Nov 2010
2×7 Posts 
Haha I thought I was the only one scrambling! Have others come to this forum looking for help too?
Thanks for the help Jason, so you are saying that if I did find a better polynomial then I would have to start from scratch again building relations? This is going to be a tough one to call because I started sieving with a pretty awful poly (e value 9.45e13) and I am starting to find some now in the 1/2e12 region. I am 10% in to the sieving. What I am most worried about is whether such a bad poly could cause the factorization to fail I have access to enough computing power for the fact that it will take longer not to matter so much, but could it cause the factorization to fail entirely? Again, thanks for your help, I've put far too much time into this to screw it all up now... 
20101120, 14:36  #5  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
1000010110111_{2} Posts 
Quote:
Just that one, as far as I'm aware. It'd be worth it for you to read that thread as well. I still think the only realistic chance is for the students to collaborate, if they're allowed to. Unless the students could make use of many school computers, either alone or working together. Last fiddled with by TimSorbet on 20101120 at 14:40 

20101120, 14:39  #6 
Jun 2003
1562_{16} Posts 
No. Just will take longer. Do you know how to estimate how many relations to collect? If you do, even now, you can test if the newer better poly can end up finishing the factorization quicker.

20101120, 14:55  #7 
Nov 2010
16_{8} Posts 
Thanks minigeek, I've read through the other thread and I'm not too worried about the competition I have to say :p. I am making use of multiple school computers (i7920s with 8GB RAM) for the sieving, whilst using the Quadro 290 GFX cards on the same machines for the polynomial selection.
@axn: I don't know how to myself, but when I run the factmsieve.py script it provides me with a miniumum number of relations. I guess what I could do would be to start sieving with the new poly, compare the rate of relation collection with that from the old poly and then just do some brief calculations to see whether the old poly with the headstart or the new one would finish first. Can anyone tell me how much time I need to allow for the matrix, square root etc steps (postprocessing?) on one of the machines I mentioned above with this 160 digit key? As that will be what tells me whether I have a fighting chance of finishing in time. 
20101120, 15:08  #8  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Quote:


20101120, 15:22  #9 
Nov 2010
2·7 Posts 
Thanks again minigeek. You don't happen to know what quad core exactly was used for the c161? I looked through the thread but couldn't find any mention of it.
The quads in the PCs I am using have hyperthreading for 8 virtual cores so as you say that could speed things up a little bit. Is msieve's code optimized for multiple cores by default or do I need to change anything? All research I've done into this has said so but can I just confirm that there is no way of splitting the post processing between multiple computers? 
20101120, 15:29  #10  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Quote:
Quote:
Code:
t <num> use at most <num> threads Quote:
Relatedly, the square root step could actually be run on multiple cores and/or computers, but msieve normally just runs it on one core (regardless of the t setting). If you're short on time, you could watch for when the linear algebra completes, then start three more square root instances so you'd be almost certain to have the factors within two hours. (it's like flipping a coin: flip one and you have a 1/2 chance of heads, flip four at once and you have a 15/16 chance of at least one heads) You'd want to use this option to specify that each instance should try different dependency numbers: Code:
nc3 [X,Y] perform only NFS square root (compute dependency numbers X through Y, 1<=X,Y<=64) Last fiddled with by TimSorbet on 20101120 at 15:35 

20101120, 15:43  #11 
Tribal Bullet
Oct 2004
2·1,789 Posts 
If you're 10% into the sieving with a bad poly and found one whose evalue is 10x better, I'd expect the sieving with the latter poly to finish ~2030% faster. The correct way to test this out is to do about 1/1000 of the sieving using the new poly with the same parameters, then estimate the relation rate and see if the total time is larger than 90% of your current estimated total time.
The postprocessing can be split across multiple computers but not easily. Latterday versions of msieve can distribute the matrix across a tightly coupled parallel computer using MPI, but you have to have MPI installed and the machines need a fast interconnect for it to be worthwhile (gigabit ethernet at a minimum). Even then the runtime for a matrix of this size is near the lower end of the range where a speedup could be expected from using, say, 4 machines in parallel. It won't be 4x faster, maybe 30% faster if you're lucky. Plus the code is a little experimental even though it has been used for huge problems. I mentioned the scrambling because other forums are also fielding questions about 160digit factorizations. I've also fielded one request through sourceforge with the same question :) Last fiddled with by jasonp on 20101120 at 15:53 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A couple newbie questions  evanmiyakawa  Information & Answers  4  20171107 01:37 
new here with a couple questions  theshark  Information & Answers  21  20140830 17:36 
2^8771 polynomial selection  fivemack  Factoring  47  20090616 00:24 
Polynomial selection  CRGreathouse  Factoring  2  20090525 07:55 
A couple questions from a new guy  Optics  Information & Answers  8  20090425 18:23 