## Quadratic Sieve

### March 19, 2013

One of the most powerful factoring methods is the quadratic sieve, invented as a “thought experiment” by Carl Pomerance in the early 1980s; it is routinely used to factor semi-primes up to a hundred digits, sometimes more. The quadratic sieve was famously used to factor RSA-129, a challenge number given by Martin Gardner in the August 1977 edition of *Scientific American*; using the methods available at the time, it was estimated that factorization would take forty quadrillion years, but in fact the number was factored in April 1994, revealing the encoded message “The magic words are squeamish ossifrage.”

Today’s exercise presents a basic version of the quadratic sieve; we will present more powerful (and more complicated) variants in future exercises. We will be following the thesis *Factoring Integers with the Self-Initializing Quadratic Sieve* by Scott Contini, which is something of a bible for implementers of the quadratic sieve; Contini’s thesis is available at http://www.crypto-world.com/documents/contini_siqs.pdf. Today’s exercise is drawn from Figure 2.1 of the thesis.

The quadratic sieve shares its basic structure with other factoring methods such as Dixon’s method and the continued fraction method that we have previously studied (today’s exercise will probably make more sense if you read those exercises first). The idea is that if *x*^{2} ≡ *y*^{2} (mod *n*) with *x* ≢ ± *y* (mod *n*), then gcd(*x*±*y*, *n*) are two factors of *n*; about half the time, the two factors will be 1 and *n*, but the other half of the time the two factors will be non-trivial. All three methods compute a series of *relations* of the form *x*^{2} ≡ *y* (mod *n*) where *y* is *smooth* over a relatively small factor base; the factored *y* are then combined using linear algebra to find *x*^{2} ≡ *y*^{2} (mod *n*) and thus perform the factorization. The three methods differ in the way they compute the relations: Dixon’s method computes them at random, the continued fraction method finds them in the convergents of the square root of *n*, and the quadratic sieve finds them by sieving a polynomial of the form *g*(*x*) = (*x* + *b*)^{2} − *n*, where *b* is the smallest integer greater than the square root of *n*. The exponent 2 in function *g* is the “quadratic” in the name of the method.

Contini gives a description of the basic quadratic sieve algorithm that we adapt here:

Compute startup data:Choosef, the upper bound for factor base primes, andm, which is half the size of the sieve. Letb= ⌈√n⌉ andg(x) = (x+b)^{2}–n. Determine the factor base primesp<fsuch that the jacobi symbol (n/p) is 1 indicating that there is a solution tot^{2}≡n(modp); also include 2 in the factor base. For each factor base primep, computet, a modular square root ofn(modp). Then compute and storesoln1=_{p}t−b(modp),soln2= −_{p}t−b(modp) andl= ⌊log_{p}p⌉ (rounding off) for each factor base primep.

Perform sieving:Initialize a sieve array to 0′s. For each odd primepin the factor base, addlto the locations_{p}soln1+_{p}ipandsoln2+_{p}ipof the sieve array fori= 0, 1, 2, …. For the primep= 2, sieve only withsoln1._{p}

Trial division:Scan sieve array for locationsxthat have accumulated a value of a least log 2x√nminus a small error term. Trial divideg(x) by the primes in the factor base. Ifg(x) factors into primes less thanf, then save smooth relation. After scanning entire sieve array, if there are more smooth relations than primes in the factor base, then go to linear algebra step. Otherwise, increaseformor both and return to sieving step.

Linear algebra:Solve the matrix as in Dixon’s method and the continued fraction method. For each null vector, construct relation of formx^{2}≡y^{2}(modn) and attempt to factornby computing gcd(x−y,n). If all null vectors fail to give a non-trivial factorization, increaseformor both and return to sieving step.

Let’s step back and look at the algorithm from a higher perspective. We are looking for relations of the form *y*^{2} ≡ *g*(*x*) (mod *n*) where *g*(*x*) is smooth so we can combine the *g*(*x*) using linear algebra to find a set of relations for which the *g*(*x*) form a perfect square, which will give us an *x* and *y* that we can use to compute a factor of *n*. Sieving the polynomial *g*(*x*) is done in the same way as sieving for primes in the Sieve of Eratosthenes; in fact, in an optimized Sieve of Eratosthenes over the odd numbers starting from 3, the sieving is performed over the polynomial 2*x*+1.

The use of logarithms in the sieving is an optimization; we could equally sieve by the primes themselves if we chose. But if we did that, we would have to sieve by all the prime powers as well as the primes, and we would have to keep track of which primes and prime powers appeared at each item of the sieve, which takes lots of memory and limits the size of the sieve. Using logarithms keeps memory consumption down, and the small error factor allows us to ignore prime powers. Note that the logarithms are rounded to integers, so we don’t need the space to store floats or doubles.

The sieving range is *b* ± *m*. Any relations found in the left half of the sieve must have a factor of −1 added to their factorizations, which is then treated as any other prime in the factor base during the linear algebra step.

The only other thing to note is that, if you are clever, when increasing *f* or *m* after a failure, you only need to compute the new pieces, assuming you saved the old pieces from sieving step.

A complete, worked example is shown on the next page.

Your task is to write a program to factor integers using the quadratic sieve as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.