Quadratic sieve
|
|
The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 110 decimal digits or so. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties.
| Contents |
Basic aim
The algorithm attempts to set up a congruence of squares modulo n (the integer to be factorized), which often leads to a factorization of n. The algorithm works in two phases: the data collection phase, where it collects information that may lead to a congruence of squares; and the data processing phase, where it puts all the data it has collected into a matrix and solves it to obtain a congruence of squares. The data collection phase can be easily parallelized to many processors, but the data processing phase requires large amounts of memory and cannot be parallelized so it is usually performed on a supercomputer for large n.
The naïve approach to finding a congruence of squares is to pick a random number, square it, and hope the least non-negative remainder modulo n is a perfect square. This approach finds a congruence of squares only rarely for large n, but when it does find one, more often than not, the factorization is complete.
The quadratic sieve is a modification of Dixon's factorization method.
The running time for the quadratic sieve (to factor an integer n) is:
- <math>O\left(\exp\left(\sqrt{\log n \log\log n}\right)\right).<math>
How QS optimizes finding congruences
The quadratic sieve attempts to find pairs of integers x and y(x) (where y(x) is a function of x) satisfying a much weaker condition than x2 ≡ y2 (mod n). It selects a set of primes called the factor base, and attempts to find x such that the least absolute remainder of y(x) = x2 mod n factorizes completely over the factor base. Such x values are said to be smooth with respect to the factor base.
The quadratic sieve speeds up the process of finding relations by taking x close to the square root of n. This ensures that y(x) will be smaller, and thus have a greater chance of being smooth.
- <math>y(x)=\left(\left\lfloor\sqrt{n}\right\rfloor+x\right)^2-n\hbox{ (where }x\hbox{ is a small integer)}<math>
- <math>y(x)\approx 2x\left\lfloor\sqrt{n}\right\rfloor+x^2<math>
This implies that y is on the order of 2x[√n]. However, it also implies that y grows linearly with the square of |x|.
We can also increase the chance of smoothness by simply increasing the size of the factor base, but that means we have to collect more relations. We must have at least as many full relations as we have primes in the factor base.
Partial relations and cycles
Even if we find a relation where y(x) is not smooth, we may be able to merge two of these partial relations to form a full one. This is only possible if the two y 's are products of the same prime(s) outside the factor base. For example, if the factor base is {2, 3, 5, 7} and n = 91 we have the partial relations:
- <math>21^2\equiv7^1\cdot11\pmod{91}<math>
- <math>29^2\equiv2^1\cdot11\pmod{91}<math>
We can multiply these together:
- <math>(21\cdot 29)^2\equiv2^1\cdot7^1\cdot11^2\pmod{91}<math>
and multiply both sides by (11−1)2 modulo 91. 11−1 modulo 91 is 58, so:
- <math>(58\cdot 21\cdot 29)^2\equiv 2^1\cdot7^1\pmod{91}<math>
- <math>14^2\equiv 2^1\cdot7^1\pmod{91}<math>
and we have a full relation. Such a full relation (obtained by combining partial relations) is called a cycle. Sometimes, forming a cycle from two partial relations leads straight to a congruence of squares, but rarely.
Checking smoothness by sieving
There are several ways to check for smoothness of the ys. The most obvious is by trial division, although this increases the running time for the data collection phase. Another method that has some acceptance is the elliptic curve method. However, in practice, a process called sieving is used.
- <math>y(x)=x^2-n<math>
- <math>y(x+kp)=(x+kp)^2-n<math>
- <math>y(x+kp)=x^2+2xkp+(kp)^2-n<math>
- <math>y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\pmod{p}<math>
Thus by solving y(x) ≡ 0 (mod p) for p, we find a whole sequence of ys which are divisible by p. This is finding a square root modulo a prime, which there exist efficient algorithms for. (This is where the quadratic sieve gets its name -- y is a quadratic polynomial in x, and the sieving process works like the Sieve of Eratosthenes.) Repeating this process for other values of p allows us to quickly find likely smooth values, without having to test for smoothness every time. When large factor bases are used (see Factoring Records below), say 500000 primes, testing for smoothness every time takes too long to be practical.
When the data processing phase begins, however, it is necessary to factorize the y-values collected, since we need to know the exponents associated with each prime of in the factor base. This is not as time-consuming as testing for smoothness by factorizing, since we already know which primes a y-value is divisible by, from the sieving. In fact, instead of trial-dividing here, one of the faster special-purpose algorithms, like Pollard's rho algorithm, might be used, since they are especially good for splitting composites with small factors.
Multiple polynomials
In practice, many different polynomials are used for y, since with only one polynomial, we will not be able to collect enough (x, y) pairs that are smooth over the factor base. The polynomials used must have a special form, since they need to be squares modulo n. The polynomials must all have a similar form to the original y(x) = x2 − n:
- <math>y(x)=Ax^2+2Bx+C\qquad A,B,C\in\mathbb{Z}<math>
A must be a square, and B2 ≡ n (mod A), with 0 ≤ B < A. C must satisfy B2 − 4AC = n. These conditions ensure that y(x) is a square.
This approach (called MPQS, Multiple Polynomial Quadratic Sieve) is ideally suited for parallelization, since each processor involved in the factorization can be given n, the factor base and a collection of polynomials, and it will have no need to communicate with the central processor until it is finished with its polynomials.
Example
Here is an example. Let n = 1817, therefore m, the floor of the square root of n, is 42. Since n is small, we will only need one polynomial: the basic one: y(x) = (x + 42)2 − 1817.
Data collection
First we choose a factor base. We need only use primes p whose Legendre symbol (n/p) is one, so we select:
- <math>F=\lbrace -1,2,7,13\rbrace.<math>
Now, for sieving purposes, we solve the congruence
- <math>x^2\equiv 1817\pmod{p}<math>
for each p in the factor base. The square roots are:
- Mod 2: 1
- Mod 7: 2 and 5
- Mod 13: 6 and 7.
This can be easily verified. Now, we list all the y(x) values for 0 ≤ x ≤ 100 (this interval can always be expanded later if we find that it does not yield enough relations). Then, for each prime p, we start at the y-value at the square root of p mod n and divide p out of that y-value. We then move p positions up in the list and repeat the procedure. This is the sieving process in action.
Once the sieving has been completed for all primes in the factor base, the positions in the list that have been reduced to 1 correspond to y-values which are smooth over F. We need at least five, and in this case the interval used has yielded four. The pairs (x, y) are:
- (1, 32), (3, 208), (9, 784), (81, 13312).
We find one more by expanding the interval as necessary (note that x can also take on negative values). Increasing the upper bound, we get:
- (103, 19208).
Data processing
We have collected enough relations to build the exponent vector matrix, but first we must factorize the y-values. This is easy, since we only have three primes to trial-divide by. Here are the factorizations:
| x | y |
| 1 | −10 • 25 • 70 • 130 |
| 3 | −10 • 24 • 70 • 131 |
| 9 | −10 • 24 • 72 • 130 |
| 81 | −10 • 210 • 70 • 131 |
| 103 | −10 • 23 • 74 • 130 |
We can now form the exponent vector matrix:
- <math>\begin{pmatrix}
0 & 5 & 0 & 0 \\ 0 & 4 & 0 & 1 \\ 0 & 4 & 2 & 0 \\ 0 & 10 & 0 & 1 \\ 0 & 3 & 4 & 0 \\ \end{pmatrix}\equiv\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}\pmod{2}<math>
Here, we can find rows that add to all-zero vectors modulo 2 by inspection. The third row (corresponding to (x, y) = (9, 784)) is already a congruence of squares, so we will try to factorize n using that.
- <math>y(x)=(x+42)^2-1817<math>
- <math>y(9)=784=28^2\equiv 51^2\pmod{1817}<math>
gcd(51 + 28, 1817) = 79 and gcd(51 − 28, 1817) = 23. These are the two non-trivial factors of 1817.
This demonstration should also serve to show that the quadratic sieve is only appropriate when n is large. For a number as small as 1817, this algorithm is overkill. Trial division could have found a factor with 9 divisions.
Factoring records
Until the discovery of the number field sieve (NFS), QS was the asymptotically-fastest known general-purpose factoring algorithm. Now, Lenstra elliptic curve factorization has the same asymptotic running time as QS (in the case where n has exactly two prime factors of equal size), but in practice, QS is faster since it uses single-precision operations instead of the multi-precision operations used by the elliptic curve method.
On April 2, 1994, the factorization of RSA-129 was completed using QS. It was a 129-digit number, the product of two large primes, one of 64 digits and the other of 65. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 mips-years, done in distributed fashion over the Internet. The data collected totaled 2GB. The data processing phase took 45 hours on Bellcore's MasPar (massively parallel) supercomputer. This was the largest published factorization by a general-purpose algorithm, until NFS was used to factor RSA-130, completed April 10, 1996. All RSA numbers factored since then have been factored using NFS.