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:
[TEX]y(x) = (\left \lceil \sqrt{n} \right \rceil + X)^{2} - n[/TEX]

Or do you use:
[TEX]y(x) = (Ax + B)^{2} - n[/TEX]

Or:
[TEX]y(x) = Ax^{2} + 2Bx + C[/TEX]

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 [TEX]B^{2} - n \equiv 0\ \textrm{(mod A)}[/TEX]

Lastly [TEX]C=\frac{B^{2} - n}{A}[/TEX]

For the sieving phase, for each prime [I]p[/I] in the factor base, do you solve the congruence: [TEX]x^{2} \equiv n\ \textrm{(mod p)}[/TEX] or do you use the polynomial generated above?

Thank You :smile:

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^2-N)/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.

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 [I]x [/I]at. With the QS, I would just use the ceiling of the square root of [I]n[/I]. However if I use that now the values for G[SIZE=1]a,b[/SIZE](x) are huge.

In his algorithm he says to store the modular square root of each prime [I]p [/I]in the factor base, but there are 2 solutions for each [I]p [/I]> 2, what am I supposed to do?

Can one be used to calculate the other? Often with quadratic residues mod p if one root is x the other is p-x.