Quadratic Sieve - The Approach

The Approach

Let x mod y denote the remainder after dividing x by y. To factorise the integer n, Fermat's method entails a search for a single number a such that a2 mod n is a square. But these a are hard to find. The quadratic sieve consists of computing a2 mod n for several a, then finding a subset of these whose product is a square. This will yield a congruence of squares.

For example, 412 mod 1649 = 32, 422 mod 1649 = 115, and 432 mod 1649 is 200. None of these is a square, but the product (32)(200) = 6400 = 802, and mod 1649, (32)(200) = (412)(432) = ((41)(43))2. Since (41)(43) mod 1649 = 114, this is a congruence of squares: 1142 ≡ 802 (mod 1649). To finish this factorization example, continue reading Congruence of squares.

But how to solve the problem of, given a set of numbers, finding a subset whose product is a square? The solution uses the concept of an exponent vector. For example, the prime-power factorization of 504 is 23325071. It can be represented by the exponent vector (3,2,0,1), which gives the exponents of 2, 3, 5, and 7 in the prime factorization. The number 490 would similarly have the vector (1,0,1,2). Multiplying the numbers is the same as componentwise adding their exponent vectors: (504)(490) has the vector (4,2,1,3).

A number is a square if every number in its exponent vector is even. For example, the vectors (3,0,0,1) and (1,2,0,1) add to (4,2,0,2), so (56)(126) is a square. Searching for a square requires knowledge only of the parity of the numbers in the vectors, so it is possible to reduce the entire vector mod 2 and perform addition of elements mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0). This is particularly efficient in practical implementations, as the vectors can be represented as bitsets and addition mod 2 reduces to bitwise XOR.

The problem is reduced to: given a set of (0,1)-vectors, find a subset which adds to the zero vector mod 2. This is a linear algebra problem; the solution is a linear dependency. It is a theorem of linear algebra that with more vectors than each vector has elements, such a dependency must exist. It can be found efficiently, for example by placing the vectors as rows in a matrix and then using Gaussian elimination, which is easily adapted to work for integers mod 2 instead of real numbers. The desired square is then the product of the numbers corresponding to those vectors.

However, simply squaring many random numbers mod n produces a very large number of different prime factors, and so very long vectors and a very large matrix. The answer is to look specifically for numbers a such that a2 mod n has only small prime factors (they are smooth numbers). They are harder to find, but using only smooth numbers keeps the vectors and matrices smaller and more tractable. The quadratic sieve searches for smooth numbers using a technique called sieving, discussed later, from which the algorithm takes its name.