 mersenneforum.org MPQS: choosing a good polynomial
 Register FAQ Search Today's Posts Mark Forums Read 2006-09-04, 09:35 #1 ThiloHarich   Nov 2005 101 Posts MPQS: choosing a good polynomial Hi, in MPQS we generate locations via a polynomial a*x + b; In MPQS we choose a = d^2 (=p_1 * p_2); In SIQS we choose a = p_1 * ... * p_k ; p_i different factors of the factor base. Since this increases k, the possible values for b (|b| = 2^(k-1)) increased as well. So the number of locations generated by one polynomial increases. What about choosing p_i as a small Factor of the Factor Base like: First polynom: p_i = 2, Second polynom: p_i = 3, .. So k is increased again, and so the number of locations generated by one polynomial increases.   2006-09-04, 13:58   #2
jasonp
Tribal Bullet

Oct 2004

1101110100012 Posts Quote:
 Originally Posted by ThiloHarich Hi, in MPQS we generate locations via a polynomial a*x + b; In MPQS we choose a = d^2 (=p_1 * p_2); In SIQS we choose a = p_1 * ... * p_k ; p_i different factors of the factor base. Since this increases k, the possible values for b (|b| = 2^(k-1)) increased as well. So the number of locations generated by one polynomial increases. What about choosing p_i as a small Factor of the Factor Base like: First polynom: p_i = 2, Second polynom: p_i = 3, .. So k is increased again, and so the number of locations generated by one polynomial increases.
k is not chosen to be large in order to make the sieving faster. k is large to allow the sieve interval to stay small (increasing the chance that random sieve values will be smooth), while putting off as long as possible the need to fully initialize for the next polynomial. Full initialization requires lots of modular arithmetic, and could dominate the cost of sieving if it happens too often.

The larger k is, the more auxiliary storage you need for switching polynomials. Also, the larger k is the smaller p_i must be. The problem here is that any p_i chosen to be a factor of 'a' values only gets one sieve root and not two, cutting its average contribution to sieve values in half. Selecting p_i too small means that the probability that random sieve values are FB-smooth actually goes down.

In practice, k is chosen to be a compromise between initializing too often and using large p_i. If you can get p_i to be 10-11 bits in size then you can essentially make k anything, but for the largest factorizations you have to increase both k and p_i to avoid huge amounts of auxiliary storage.

jasonp   2006-09-04, 23:57 #3 ThiloHarich   Nov 2005 101 Posts Since we use a = p^k and p is small, can't we solve the equation b^2 = n mod p^k by solving the equation b^2 = n mod p and lifting the solution via Hensels Lemma? This is what the MPQS does with k=2. Doing so computing the solutions for a = p^k should be cheap, and changing the polynomial should be cheap as well.   2006-09-05, 01:45   #4
jasonp
Tribal Bullet

Oct 2004

33×131 Posts Quote:
 Originally Posted by ThiloHarich Since we use a = p^k and p is small, can't we solve the equation b^2 = n mod p^k by solving the equation b^2 = n mod p and lifting the solution via Hensels Lemma? This is what the MPQS does with k=2. Doing so computing the solutions for a = p^k should be cheap, and changing the polynomial should be cheap as well.
You can do that, but would it let you self-initialize? With different p_i, the chinese remainder theorem lets you build different b values by adding together different combinations of +- F(p_i), for some function F. If all the p_i are the same, wouldn't their F values be identical? I can't see how you would get more than one b value from a particular p.

jasonp   2006-09-05, 07:51 #5 ThiloHarich   Nov 2005 101 Posts You are right. Theory tells us that there is only one solution for x^2 = N mod 2^k (if 2 is in the FB).  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post RienS Hardware 17 2014-11-18 22:58 wombatman Msieve 123 2013-08-27 11:27 Sam Kennedy Factoring 3 2012-12-22 15:41 smoking81 Factoring 10 2007-10-02 12:30 R1zZ1 Factoring 2 2007-02-02 06:45

All times are UTC. The time now is 20:32.

Fri May 7 20:32:18 UTC 2021 up 29 days, 15:13, 1 user, load averages: 9.04, 7.49, 4.73