Go Back > Factoring Projects > Factoring

Thread Tools
Old 2012-12-18, 23:52   #1
Sam Kennedy
Sam Kennedy's Avatar
Oct 2012

2·41 Posts
Default 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

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
Sam Kennedy is offline   Reply With Quote
Old 2012-12-19, 02:14   #2
Tribal Bullet
jasonp's Avatar
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.
jasonp is offline   Reply With Quote
Old 2012-12-22, 01:42   #3
Sam Kennedy
Sam Kennedy's Avatar
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?
Sam Kennedy is offline   Reply With Quote
Old 2012-12-22, 15:41   #4
Just call me Henry
henryzz's Avatar
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.
henryzz is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing MPQS: SOS! smoking81 Factoring 10 2007-10-02 12:30
poly selection in MPQS bsquared Factoring 3 2007-02-28 14:22
Feedback for new MPQS utility sought jasonp Msieve 308 2007-02-21 05:43
Linear algebra in MPQS R1zZ1 Factoring 2 2007-02-02 06:45
MPQS: choosing a good polynomial 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.