MPQS: choosing a good polynomial

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

[jasonp]

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

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

[jasonp]

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

[ThiloHarich]

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