Quadratic sieve

Last updated

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve. [1]

Contents

Basic aim

The algorithm attempts to set up a congruence of squares modulo n (the integer to be factorized), which often leads to a factorization of n. The algorithm works in two phases: the data collection phase, where it collects information that may lead to a congruence of squares; and the data processing phase, where it puts all the data it has collected into a matrix and solves it to obtain a congruence of squares. The data collection phase can be easily parallelized to many processors, but the data processing phase requires large amounts of memory, and is difficult to parallelize efficiently over many nodes or if the processing nodes do not each have enough memory to store the whole matrix. The block Wiedemann algorithm can be used in the case of a few systems each capable of holding the matrix.

The naive approach to finding a congruence of squares is to pick a random number, square it, divide by n and hope the least non-negative remainder is a perfect square. For example, . This approach finds a congruence of squares only rarely for large n, but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of Fermat's factorization method.

The quadratic sieve is a modification of Dixon's factorization method. The general running time required for the quadratic sieve (to factor an integer n) is conjectured to be

in the L-notation. [2] The constant e is the base of the natural logarithm.

The approach

To factorize the integer n, Fermat's method entails a search for a single number a, n1/2 < a < n−1, such that the remainder of a2 divided by n is a square. But these a are hard to find. The quadratic sieve consists of computing the remainder of a2/n for several a, then finding a subset of these whose product is a square. This will yield a congruence of squares.

For example, consider attempting to factor the number 1649. We have: . None of the integers is a square, but the product is a square. We also had

since . The observation that thus gives a congruence of squares

Hence for some integer . We can then factor

using the Euclidean algorithm to calculate the greatest common divisor.

So the problem has now been reduced to: given a set of integers, find a subset whose product is a square. By the fundamental theorem of arithmetic, any positive integer can be written uniquely as a product of prime powers. We do this in a vector format; for example, the prime-power factorization of 504 is 23325071, it is therefore represented by the exponent vector (3,2,0,1). Multiplying two integers then corresponds to adding their exponent vectors. A number is a square when its exponent vector is even in every coordinate. For example, the vectors (3,2,0,1) + (1,0,0,1) = (4,2,0,2), so (504)(14) is a square. Searching for a square requires knowledge only of the parity of the numbers in the vectors, so it is sufficient to compute these vectors mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0). So given a set of (0,1)-vectors, we need to find a subset which adds to the zero vector mod 2.

This is a linear algebra problem since the ring can be regarded as the Galois field of order 2, that is we can divide by all non-zero numbers (there is only one, namely 1) when calculating modulo 2. It is a theorem of linear algebra that with more vectors than each vector has entries, a linear dependency always exists. It can be found by Gaussian elimination. However, simply squaring many random numbers mod n produces a very large number of different prime factors, and thus very long vectors and a very large matrix. The trick 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.

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 ai such that bi = (ai2 mod n) is B-smooth.
  3. Factor the bi 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 aitogether and give the result mod n the name a; similarly, multiply the bi 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.

How QS optimizes finding congruences

The quadratic sieve attempts to find pairs of integers x and y(x) (where y(x) is a function of x) satisfying a much weaker condition than x2y2 (mod n). It selects a set of primes called the factor base, and attempts to find x such that the least absolute remainder of y(x) = x2 mod n factorizes completely over the factor base. Such y values are said to be smooth with respect to the factor base.

The factorization of a value of y(x) that splits over the factor base, together with the value of x, is known as a relation. The quadratic sieve speeds up the process of finding relations by taking x close to the square root of n. This ensures that y(x) will be smaller, and thus have a greater chance of being smooth.

This implies that y is on the order of 2x[n]. However, it also implies that y grows linearly with x times the square root of n.

Another way to increase the chance of smoothness is by simply increasing the size of the factor base. However, it is necessary to find at least one smooth relation more than the number of primes in the factor base, to ensure the existence of a linear dependency.

Partial relations and cycles

Even if for some relation y(x) is not smooth, it may be possible to merge two of these partial relations to form a full one, if the two y's are products of the same prime(s) outside the factor base. [Note that this is equivalent to extending the factor base.] For example, if the factor base is {2, 3, 5, 7} and n = 91, there are partial relations:

Multiply these together:

and multiply both sides by (111)2 modulo 91. 111 modulo 91 is 58, so:

producing a full relation. Such a full relation (obtained by combining partial relations) is called a cycle. Sometimes, forming a cycle from two partial relations leads directly to a congruence of squares, but rarely.

Checking smoothness by sieving

There are several ways to check for smoothness of the ys. The most obvious is by trial division, although this increases the running time for the data collection phase. Another method that has some acceptance is the elliptic curve method (ECM). In practice, a process called sieving is typically used. If f(x) is the polynomial we have

Thus solving f(x) ≡ 0 (mod p) for x generates a whole sequence of numbers y for which y=f(x), all of which are divisible by p. This is finding a square root modulo a prime, for which there exist efficient algorithms, such as the Shanks–Tonelli algorithm. (This is where the quadratic sieve gets its name: y is a quadratic polynomial in x, and the sieving process works like the Sieve of Eratosthenes.)

The sieve starts by setting every entry in a large array A[] of bytes to zero. For each p, solve the quadratic equation mod p to get two roots α and β, and then add an approximation to log(p) to every entry for which y(x) = 0 mod p ... that is, A[kp + α] and A[kp + β]. It is also necessary to solve the quadratic equation modulo small powers of p in order to recognise numbers divisible by small powers of a factor-base prime.

At the end of the factor base, any A[] containing a value above a threshold of roughly log(x2n) will correspond to a value of y(x) which splits over the factor base. The information about exactly which primes divide y(x) has been lost, but it has only small factors, and there are many good algorithms for factoring a number known to have only small factors, such as trial division by small primes, SQUFOF, Pollard rho, and ECM, which are usually used in some combination.

There are many y(x) values that work, so the factorization process at the end doesn't have to be entirely reliable; often the processes misbehave on say 5% of inputs, requiring a small amount of extra sieving.

Example of basic sieve

This example will demonstrate standard quadratic sieve without logarithm optimizations or prime powers. Let the number to be factored N = 15347, therefore the ceiling of the square root of N is 124. Since N is small, the basic polynomial is enough: y(x) = (x + 124)2 − 15347.

Data collection

Since N is small, only four primes are necessary. The first four primes p for which 15347 has a square root mod p are 2, 17, 23, and 29 (in other words, 15347 is a quadratic residue modulo each of these primes). These primes will be the basis for sieving.

Now we construct our sieve of and begin the sieving process for each prime in the basis, choosing to sieve the first 0 ≤ X < 100 of Y(X):

The next step is to perform the sieve. For each p in our factor base solve the equation

to find the entries in the array V which are divisible by p.

For solve to get the solution .

Thus, starting at X=1 and incrementing by 2, each entry will be divisible by 2. Dividing each of those entries by 2 yields

Similarly for the remaining primes p in the equation is solved. Note that for every p > 2, there will be 2 resulting linear equations due to there being 2 modular square roots.

Each equation results in being divisible by p at x=a and each pth value beyond that. Dividing V by p at a, a+p, a+2p, a+3p, etc., for each prime in the basis finds the smooth numbers which are products of unique primes (first powers).

Any entry of V that equals 1 corresponds to a smooth number. Since , , and equal one, this corresponds to:

X + 124Yfactors
1242920 • 170 • 230 • 291
12778221 • 171 • 231 • 290
1952267821 • 171 • 231 • 291

Matrix processing

Since smooth numbers Y have been found with the property , the remainder of the algorithm follows equivalently to any other variation of Dixon's factorization method.

Writing the exponents of the product of a subset of the equations

as a matrix yields:

A solution to the equation is given by the left null space, simply

Thus the product of all three equations yields a square (mod N).

and

So the algorithm found

Testing the result yields GCD(3070860 - 22678, 15347) = 103, a nontrivial factor of 15347, the other being 149.

This demonstration should also serve to show that the quadratic sieve is only appropriate when n is large. For a number as small as 15347, this algorithm is overkill. Trial division or Pollard rho could have found a factor with much less computation.

Multiple polynomials

In practice, many different polynomials are used for y so that when y(x) starts to become large, resulting in poor density of smooth y, this growth can be reset by switching polynomials. As usual, we choose y(x) to be a square modulo n, but now with the form

is chosen such that , so for some . The polynomial y(x) can then be written as . If A is a square or a smooth number, then only the factor has to be checked for smoothness.

This approach, called Multiple Polynomial Quadratic Sieve (MPQS), is ideally suited for parallelization, since each processor involved in the factorization can be given n, the factor base and a collection of polynomials, and it will have no need to communicate with the central processor until it has finished sieving with its polynomials.

Large primes

One large prime

If, after dividing by all the factors less than A, the remaining part of the number (the cofactor) is less than A2, then this cofactor must be prime. In effect, it can be added to the factor base, by sorting the list of relations into order by cofactor. If y(a) = 7*11*23*137 and y(b) = 3*5*7*137, then y(a)y(b) = 3*5*11*23 * 72 * 1372. This works by reducing the threshold of entries in the sieving array above which a full factorization is performed.

More large primes

Reducing the threshold even further, and using an effective process for factoring y(x) values into products of even relatively large primes - ECM is superb for this - can find relations with most of their factors in the factor base, but with two or even three larger primes. Cycle finding then allows combining a set of relations sharing several primes into a single relation.

Parameters from realistic example

To illustrate typical parameter choices for a realistic example on a real implementation including the multiple polynomial and large prime optimizations, the tool msieve was run on a 267-bit semiprime, producing the following parameters:

Factoring records

Until the discovery of the number field sieve (NFS), QS was the asymptotically fastest known general-purpose factoring algorithm. Now, Lenstra elliptic curve factorization has the same asymptotic running time as QS (in the case where n has exactly two prime factors of equal size), but in practice, QS is faster since it uses single-precision operations instead of the multi-precision operations used by the elliptic curve method.

On April 2, 1994, the factorization of RSA-129 was completed using QS. It was a 129-digit number, the product of two large primes, one of 64 digits and the other of 65 digits. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 MIPS-years, done in distributed fashion over the Internet. The data collected totaled 2GB. The data processing phase took 45 hours on Bellcore's (now Telcordia Technologies) MasPar (massively parallel) supercomputer. This was the largest published factorization by a general-purpose algorithm, until NFS was used to factor RSA-130, completed April 10, 1996. All RSA numbers factored since then have been factored using NFS.

The current QS factorization record is the 140-digit (463-bit) RSA-140, which was factored by Patrick Konsor in June 2020 using approximately 6,000 core hours over 6 days. [3]

Implementations

See also

Related Research Articles

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4.

<span class="mw-page-title-main">Jacobi symbol</span> Generalization of the Legendre symbol in number theory

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by a polynomial.

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Shanks' square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2n, where p is a prime: that is, to find a square root of n modulo p.

In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.

In number theory, an aurifeuillean factorization, named after Léon-François-Antoine Aurifeuille, is factorization of certain integer values of the cyclotomic polynomials. Because cyclotomic polynomials are irreducible polynomials over the integers, such a factorization cannot come from an algebraic factorization of the polynomial. Nevertheless, certain families of integers coming from cyclotomic polynomials have factorizations given by formulas applying to the whole family, as in the examples below.

In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra, and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.

<span class="mw-page-title-main">Berlekamp–Rabin algorithm</span> Method in number theory

In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over the field with elements. The method was discovered by Elwyn Berlekamp in 1970 as an auxiliary to the algorithm for polynomial factorization over finite fields. The algorithm was later modified by Rabin for arbitrary finite fields in 1979. The method was also independently discovered before Berlekamp by other researchers.

Kunerth's algorithm is an algorithm for computing the modular square root of a given number. The algorithm does not require the factorization of the modulus, and relies on modular operations that is often easy when the given number is prime.

This is a glossary of concepts and results in number theory, a field of mathematics. Concepts and results in arithmetic geometry and diophantine geometry can be found in Glossary of arithmetic and diophantine geometry.

References

  1. Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.
  2. Pomerance, Carl (December 1996). "A Tale of Two Sieves" (PDF). Notices of the AMS . Vol. 43, no. 12. pp. 1473–1485.
  3. "Useless Accomplishment: RSA-140 Factorization with Quadratic Sieve - mersenneforum.org". www.mersenneforum.org. Retrieved 2020-07-07.