Computer science

The Quadratic Sieve Factoring Algorithm
Eric Landquist MATH 488: Cryptographic Algorithms December 14, 2001

1

Introduction

Mathematicians have been attempting to find better and faster ways to factor composite numbers since the beginning of time. Initially this involved dividing a number by larger and larger primes until you had the factorization. This trial division was not improvedupon until Fermat applied the factorization of the difference of two squares: a2 − b2 = (a − b)(a + b). In his method, we begin with the number to be factored: n. We find the smallest square larger than n, and test to see if the difference is square. If so, then we can apply the trick of factoring the difference of two squares to find the factors of n. If the difference is not a perfect square, then wefind the next largest square, and repeat the process. While Fermat’s method is much faster than trial division, when it comes to the real world of factoring, for example factoring an RSA modulus several hundred digits long, the purely iterative method of Fermat is too slow. Several other methods have been presented, such as the Elliptic Curve Method discovered by H. Lenstra in 1987 and a pair ofprobabilistic methods by Pollard in the mid 70’s, the p − 1 method and the ρ method. The fastest algorithms, however, utilize the same trick as Fermat, examples of which are the Continued Fraction Method, the Quadratic Sieve (and it variants), and the Number Field Sieve (and its variants). The exception to this is the Elliptic Curve Method, which runs almost as fast as the Quadratic Sieve. The remainderof this paper focuses on the Quadratic Sieve Method.

2

The Quadratic Sieve

The Quadratic Sieve, hereafter simply called the QS, was invented by Carl Pomerance in 1981, extending earlier ideas of Kraitchik and Dixon. The QS was the fastest known factoring algorithm until the Number Field Sieve was discovered in 1993. Still the QS is faster than the Number Field Sieve for numbers up to 110digits long.

1

3

How it Works

If n is the number to be factored, the QS attemps to find two numbers x and y such that x ≡ ±y (mod n) and x2 ≡ y 2 (mod n). This would imply that (x − y)(x + y) ≡ 0 (mod n), and we simply compute (x − y, n) using the Euclidean Algorithm to see if this is a nontrivial divisor. There is at least 1 a 2 chance that the factor will be nontrivial. Our firststep in doing so is to define √ Q(x) = (x + n )2 − n = x2 − n, ˜ and compute Q(x1 ), Q(x2 ), . . . , Q(xk ). Determining the xi will be explained below. From the evaluations of Q(x), we want to pick a subset such that Q(xi1 )Q(xi2 ) . . . Q(xir ) is a square, y 2 . Then note that for all x, Q(x) ≡ x2 ˜ (mod n). So what we have then is that Q(xi1 )Q(xi2 ) . . . Q(xir ) ≡ (xi1 xi2 . . . xir )2 (mod n).And if the conditions above hold, then we have factors of n.

3.1

Setting up a Factor Base and a Sieving Interval

With the basic outline of the QS in place, we need an efficient way to determine our xi , and to get a product of the Q(xi ) to be a square. Now to check to see if the product is a square, the exponents of the prime factors of the product need to all be even. So we will needto factor each of the Q(xi ). Therefore, we want them to be small and to factor over a fixed set of small prime numbers (including -1), which we call our factor base. To make Q(x) small, we need to select x close to 0, so we set a bound M and only consider values of x over the sieving interval [−M, M ]. (Alternatively, we √ could have √ 2 defined Q(x) = x −n and let the sieving interval be [ n −M, n+M ].) Now if x is in this sieving interval, and if some prime p divides Q(x), then √ (x − n )2 ≡ n (mod p), so n is a quadratic residue (mod p). So the primes in our factor base must be primes such that the Legendre symbol n p 2 = 1.

A second criterion for these primes is that they should be less than some bound B, which depends on the size of n. We will discuss this when we analyze the...