20060904, 09:35  #1 
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^(k1)) 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. 
20060904, 13:58  #2  
Tribal Bullet
Oct 2004
110111010001_{2} Posts 
Quote:
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 FBsmooth 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 1011 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 

20060904, 23:57  #3 
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. 
20060905, 01:45  #4  
Tribal Bullet
Oct 2004
3^{3}×131 Posts 
Quote:
jasonp 

20060905, 07:51  #5 
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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Good aircooler good enough for overclocked i75820K  RienS  Hardware  17  20141118 22:58 
Choosing the best polynomial  wombatman  Msieve  123  20130827 11:27 
The MPQS differs from the QS  Sam Kennedy  Factoring  3  20121222 15:41 
Implementing MPQS: SOS!  smoking81  Factoring  10  20071002 12:30 
Linear algebra in MPQS  R1zZ1  Factoring  2  20070202 06:45 