Quadratic Sieve - The Algorithm

The Algorithm

To summarize, the basic quadratic sieve algorithm has these main steps:

1. Choose a smoothness bound B. The number π(B), denoting the number of prime numbers less than B, will control both the length of the vectors and the number of vectors needed.
2. Use sieving to locate π(B) + 1 numbers a_i such that b_i=(a_i2 mod n) is B-smooth.
3. Factor the b_i and generate exponent vectors mod 2 for each one.
4. Use linear algebra to find a subset of these vectors which add to the zero vector. Multiply the corresponding a_i together naming the result mod n: a and the b_i together which yields a B-smooth square b2.
5. We are now left with the equality a2=b2 mod n from which we get two square roots of (a2 mod n), one by taking the square root in the integers of b2 namely b, and the other the a computed in step 4.
6. We now have the desired identity: . Compute the GCD of n with the difference (or sum) of a and b. This produces a factor, although it may be a trivial factor (n or 1). If the factor is trivial, try again with a different linear dependency or different a.

The remainder of this article explains details and extensions of this basic algorithm.