mersenneforum.org The MPQS differs from the QS
 Register FAQ Search Today's Posts Mark Forums Read

 2012-12-18, 23:52 #1 Sam Kennedy     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: $y(x) = (\left \lceil \sqrt{n} \right \rceil + X)^{2} - n$ Or do you use: $y(x) = (Ax + B)^{2} - n$ Or: $y(x) = Ax^{2} + 2Bx + C$ 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 $B^{2} - n \equiv 0\ \textrm{(mod A)}$ Lastly $C=\frac{B^{2} - n}{A}$ For the sieving phase, for each prime p in the factor base, do you solve the congruence: $x^{2} \equiv n\ \textrm{(mod p)}$ or do you use the polynomial generated above? Thank You Last fiddled with by Sam Kennedy on 2012-12-19 at 00:03
 2012-12-19, 02:14 #2 jasonp 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^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.
 2012-12-22, 01:42 #3 Sam Kennedy     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?
 2012-12-22, 15:41 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT) 130728 Posts Can one be used to calculate the other? Often with quadratic residues mod p if one root is x the other is p-x.

 Similar Threads Thread Thread Starter Forum Replies Last Post smoking81 Factoring 10 2007-10-02 12:30 bsquared Factoring 3 2007-02-28 14:22 jasonp Msieve 308 2007-02-21 05:43 R1zZ1 Factoring 2 2007-02-02 06:45 ThiloHarich Factoring 4 2006-09-05 07:51

All times are UTC. The time now is 03:18.

Tue Aug 4 03:18:57 UTC 2020 up 17 days, 23:05, 0 users, load averages: 1.34, 1.48, 1.52