Computer Security and Cryptography

13.7 THE QUADRATIC SIEVE (QS)

Dixon's method may be inefficient, often requiring a large number of random terms {u_i} in order to construct a pair of integers x, y such that x² = y² (modulo N). The quadratic sieve refines Dixon's idea of searching only for pairs (x, y) close to m ≈ √N. When m = √N and x is small compared to m, then

is of the order √N and it is reasonable to expect the prime factors of q(x) to be small.

The following observation will be used; if a prime p divides q(x) so that

then

so that N is a quadratic residue of p and only these primes occur in the factorization of q(x).

The quadratic sieve consists of the following steps:

QS0.	Select a Factor Base: The factor base = {p0, p1, p2, …, pt} contains p0 = −1 and p1 = 2; the remaining terms are the next t − 1 primes p2, p3, …, pt satisfying n is a quadratic residue modulo pi.
QS1.	Find Smooth x-Values: An integer x is ...