20121218, 23:52  #1 
Oct 2012
2·41 Posts 
The MPQS differs from the QS
(Sorry about the typo in the title, I'm tired)
I'm starting to work on a version of the MPQS now, and I'm just trying to understand how it differs from my current implementation of the QS. For the data collection phase, do you still use the QS polynomial: Or do you use: Or: When generating a polynomial, do you take an odd prime from the factor base, square it, and make A equal to this value. Then set B so that Lastly For the sieving phase, for each prime p in the factor base, do you solve the congruence: or do you use the polynomial generated above? Thank You Last fiddled with by Sam Kennedy on 20121219 at 00:03 
20121219, 02:14  #2 
Tribal Bullet
Oct 2004
3,527 Posts 
The important thing to remember about MPQS is that you are sampling the QS polynomial at widely separated points on an arithmetic progression. The factor base is the same, and any x in your second y(x) can be mapped to some X in the first y(X).
You want to choose A, B, C and x so that MPQS sieves over  values of the standard QS polynomial  that are divisible by some large number To address the first requirement, you sieve the polynomial (Ax+B)^2  N. Pretend that the large number dividing sieve values is the square of a prime Q. You want it to be a square because at the end when you multiply relations together you have to take the square root of each relation. Q needs to be a factor of sieve values, so it has to be capable of being put in the factor base, but in general Q will be so large that it is pointless to treat it like just another factor base prime. So the arithmetic progression is given by Ax+B. Let A be Q^2 and choose B to be a square root mod Q^2 (computing this doesn't take much time but is pretty complex). Then since you know that Q^2 divides all the sieve values, you can ignore a factor of Q^2 when sieving. (Ax+B)^2  N = A(Ax^2 + 2Bx + C), for C = (B^2N)/A and B chosen so that the division is exact. So the sieving can be over the quantity in parentheses, which is of size about x*sqrt(N) when A and B are chosen optimally. This size bound starts off worse than the size bound for sieving the QS polynomial directly, but this is peanuts compared to the speedup we get from MPQS being able to switch to a different Q when x starts to get large. Scott Contini's dissertation on SIQS goes into more of the details. 
20121222, 01:42  #3 
Oct 2012
2·41 Posts 
I've been reading Scott Contini's dissertation quite a lot, and I think I'm doing everything correctly, however I'm unsure of what value to start x at. With the QS, I would just use the ceiling of the square root of n. However if I use that now the values for Ga,b(x) are huge.
In his algorithm he says to store the modular square root of each prime p in the factor base, but there are 2 solutions for each p > 2, what am I supposed to do? 
20121222, 15:41  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
13072_{8} Posts 
Can one be used to calculate the other? Often with quadratic residues mod p if one root is x the other is px.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Implementing MPQS: SOS!  smoking81  Factoring  10  20071002 12:30 
poly selection in MPQS  bsquared  Factoring  3  20070228 14:22 
Feedback for new MPQS utility sought  jasonp  Msieve  308  20070221 05:43 
Linear algebra in MPQS  R1zZ1  Factoring  2  20070202 06:45 
MPQS: choosing a good polynomial  ThiloHarich  Factoring  4  20060905 07:51 