The quadratic sieve algorithm (QS) is a modern 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 110 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 Dixon's factorization method. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers larger than 100 digits. ... The integers are commonly denoted by the above symbol. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ... In number theory, Dixons factorization method (also Dixons algorithm) is a general-purpose integer factorization algorithm. ...

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 cannot be parallelized so it is usually performed on a supercomputer for large n. In number theory, a congruence of squares modulo an integer n is an equality . Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ... Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ... A supercomputer is a computer that leads the world in terms of processing capacity, particularly speed of calculation, at the time of its introduction. ...

The naïve approach to finding a congruence of squares is to pick a random number, square it, and hope the least non-negative remainder modulo n is a perfect square (in the integers). For example, if we square 80 mod 5959, we get 441, which is 21². 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. Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... The term perfect square is used in mathematics in two meanings: an integer which is the square of some other integer, i. ... With Fermats factoring method, one tries to represent an odd integer as the difference of two squares: . That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Furthermore, each odd number has such a representation. ...

The quadratic sieve is a modification of Dixon's factorization method. In number theory, Dixons factorization method (also Dixons algorithm) is a general-purpose integer factorization algorithm. ...

The general running time required for the quadratic sieve (to factor an integer n) is:

The constant e is usually used as the base of the logarithm.

The approach

Let x mod y denote the remainder after dividing x by y. In Fermat's method we search for a single number a such that a² mod n is a square. But these a are hard to find. In the quadratic sieve, we compute a² mod n for several a, then find a subset of these whose product is a square. This will yield a congruence of squares. Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ... With Fermats factoring method, one tries to represent an odd integer as the difference of two squares: . That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Furthermore, each odd number has such a representation. ... In number theory, a congruence of squares modulo an integer n is an equality . Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. ...

For example, 41² mod 1649 = 32, 42² mod 1649 = 115, and 43² mod 1649 is 200. None of these is a square, but the product (32)(200) = 6400 = 80². On the other hand, mod 1649 we have (32)(200) = (41²)(43²) = ((41)(43))². Since (41)(43) mod 1649 = 114, we have a congruence of squares: 114² ≡ 80² (mod 1649).

But how do we solve the problem of, given a set of numbers, finding a subset whose product is a square? We begin with the concept of an exponent vector. Say we have the number 504. Its prime-power factorization is 2³3²7. We might represent this with the exponent vector (3,2,0,1), which gives the exponents of 2, 3, 5, and 7 in the prime factorization. The number 490 would similarly have the vector (1,0,1,2). When we multiply the numbers, it's the same as componentwise adding their exponent vectors: (504)(490) has the vector (4,2,1,3). A vector in physics and engineering typically refers to a quantity that has close relationship to the spatial coordinates, informally described as an object with a magnitude and a direction. The word vector is also now used for more general concepts (see also vector and generalizations below), but in this... In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 is either a prime number or can be written as a product of prime numbers. ...

Now, we observe that a number is a square iff every number in its exponent vector is even. For example, the vectors (3,0,0,1) and (1,2,0,1) add to (4,2,0,2). This tells us that (56)(126) is a square. Because we're only distinguishing between the parity of the numbers in the vectors, we can reduce the entire vector mod 2 and perform addition of elements mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0). This is particularly efficient in practical implementations, as the vectors can be represented as bitsets and addition mod 2 reduces to bitwise XOR. IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation... Look up Parity in Wiktionary, the free dictionary Parity is a concept of equality of status or functional equivalence. ... A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...

So we've reduced our problem to: given a set of (0,1)-vectors, find a subset which add to the zero vector mod 2. This is a linear algebra problem: we're simply looking for a linear dependency. It is a theorem of linear algebra that as long as we have more vectors than each vector has elements, such a dependency must exist. We can efficiently find it, for example by placing the vectors as columns in a matrix and then using Gaussian elimination, which is easily adapted to work for integers mod 2 instead of real numbers. Once we find it, we simply multiply the numbers corresponding to those vectors and obtain the square we seek. In linear algebra and related areas of mathematics, the null vector or zero vector in a vector space is the uniquely-determined vector, usually written 0, that is the identity element for vector addition. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear transformations, and systems of linear equations. ... In linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ... In mathematics, Gaussian elimination (not to be confused with Gauss–Jordan elimination), named after Carl Friedrich Gauss, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... In mathematics, the real numbers may be described informally in several different ways. ...

The one catch is that if we just square a bunch of random numbers mod n, we're going to end up with a very large number of different prime factors, and so very long vectors and a very large matrix. To solve this issue, we specifically look for numbers a such that a² mod n only has small prime factors (they are smooth numbers). They are harder to find, but by just using these numbers, we can get away with much smaller vectors, and so we don't need as many of them and we can save a lot of time in the matrix stage. We do this using a technique called sieving, discussed later, from which the algorithm takes its name. It has been suggested that this article or section be merged into randomness. ... In number theory, a positive integer m is called B-smooth if all prime factors of m are such that . For example, 22335654 is 5-smooth since none of its prime factors are greater than 5. ... Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. ...

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 our vectors and the number of vectors we must find.
2. Use sieving to locate π(B) + 1 numbers a such that a² mod n is B-smooth. Factor these numbers and generate exponent vectors mod 2 for each one.
3. Use linear algebra to find a subset of these vectors which add to the zero vector. Multiply the corresponding B-smooth numbers to get a square.
4. Find two square roots of the square mod n, one by taking its square root in the integers, and one by multiplying the original a corresponding to the B-smooth numbers whose product is the square.
5. Compute the GCD of n with the difference (or sum) of the two square roots. This produces a factor, although it may be a trivial factor (n or 1). If a trivial factor is encountered, we 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 x² ≡ y² (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) = x² mod n factorizes completely over the factor base. Such x values are said to be smooth with respect to the factor base. In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors. ...

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.

We can also increase the chance of smoothness by simply increasing the size of the factor base. This does not mean, that we have to collect more relations. But, we must have at least one smooth relation more as we have primes in the factor base, if we want to be sure to find a nontrivial solution for the linear equations.

Partial relations and cycles

Even if we find a relation where y(x) is not smooth, we may be able to merge two of these partial relations to form a full one. This is only possible if the two y 's are products of the same prime(s) outside the factor base. For example, if the factor base is {2, 3, 5, 7} and n = 91 we have the partial relations:

We can multiply these together:

and multiply both sides by (11⁻¹)² modulo 91. 11⁻¹ modulo 91 is 58, so:

and we have 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 straight 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. However, in practice, a process called sieving is used. Trial division is the simplest and easiest to understand of the integer factorization algorithms. ... The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves. ...

y(x) = x² − n

y(x + kp) = (x + kp)² − n

y(x + kp) = x² + 2xkp + (kp)² − n

Thus by solving y(x) ≡ 0 (mod p) for p, we find a whole sequence of ys which are divisible by p. This is finding a square root modulo a prime, which there exist efficient algorithms for, for example 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.) Repeating this process for other values of p allows us to quickly find likely smooth values, without having to test for smoothness every time. When large factor bases are used (see Factoring Records below), say 500000 primes, testing for smoothness every time takes too long to be practical. The Shanks-Tonelli algorithm is used within modular arithmetic to solve a congruence of the form where n is a quadratic residue (mod p), and is prime; typically, . When , it is much more efficient to use the following identity: . Shanks-Tonelli cannot be used for composite moduli, which is a... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ...

When the data processing phase begins, however, it is necessary to factorize the y-values collected, since we need to know the exponents associated with each prime of in the factor base. This is not as time-consuming as testing for smoothness by factorizing, since we already know which primes a y-value is divisible by, from the sieving. In fact, instead of trial-dividing here, one of the faster special-purpose algorithms, like Pollard's rho algorithm, might be used, since they are especially good for splitting composites with small factors. Pollards rho algorithm is a special-purpose integer factorization algorithm. ...

Multiple polynomials

In practice, many different polynomials are used for y, since with only one polynomial, we will not be able to collect enough (x, y) pairs that are smooth over the factor base. The polynomials used must have a special form, since they need to be squares modulo n. The polynomials must all have a similar form to the original y(x) = x² − n: In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...

Assuming B² − n is a multiple of A, so that B² − n = AC the polynomial y(x) can be written as y(x) = A * (Ax² + 2Bx + C). If then A is a square, only the factor (Ax² + 2Bx + C) have to be considered.

This approach (called MPQS, Multiple Polynomial Quadratic Sieve) 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 is finished with its polynomials. In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result. ... CPU redirects here. ...

Example

The factual accuracy of this article is disputed. Please see the relevant discussion on the talk page.

Here is an example. Let n = 1817, therefore m, the floor of the square root of n, is 42. Since n is small, we will only need one polynomial: the basic one: y(x) = (x + 42)² − 1817. Image File history File links Circle-question-red. ...

Data collection

First we choose a factor base. We need only use primes p whose Legendre symbol (n/p) is one, so we select: The Legendre symbol is used by mathematicians in the area of number theory, particularly in the fields of factorization and quadratic residues. ...

F = { − 1,2,7,13}.

Now, for sieving purposes, we solve the congruence

for each p in the factor base. The square roots are:

Mod 2: 1

Mod 7: 2 and 5

Mod 13: 6 and 7.

This can be easily verified. Now, we list all the y(x) values for 0 ≤ x ≤ 100 (this interval can always be expanded later if we find that it does not yield enough relations). Then, for each prime p, we start at the y-value at the square root of n mod p and divide p out of that y-value. We then move p positions up in the list and repeat the procedure. This is the sieving process in action.

Once the sieving has been completed for all primes in the factor base, the positions in the list that have been reduced to 1 correspond to y-values which are smooth over F. We need at least five, and in this case the interval used has yielded four. The pairs (x, y) are:

(1, 32), (3, 208), (9, 784), (81, 13312).

We find one more by expanding the interval as necessary (note that x can also take on negative values). Increasing the upper bound, we get:

(103, 19208).

Data processing

We have collected enough relations to build the exponent vector matrix, but first we must factorize the y-values. This is easy, since we only have three primes to trial-divide by. Here are the factorizations:

We can now form the exponent vector matrix:

Here, we can find rows that add to all-zero vectors modulo 2 by inspection. The third row (corresponding to (x, y) = (9, 784)) is already a congruence of squares, so we will try to factorize n using that.

y(x) = (x + 42)² − 1817

gcd(51 + 28, 1817) = 79 and gcd(51 − 28, 1817) = 23. These are the two non-trivial factors of 1817.

This demonstration should also serve to show that the quadratic sieve is only appropriate when n is large. For a number as small as 1817, this algorithm is overkill. Trial division could have found a factor with 9 divisions. Trial division is the simplest and easiest to understand of the integer factorization algorithms. ...

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. In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers larger than 100 digits. ... The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves. ... It has been suggested that this article or section be merged into IEEE floating-point standard. ...

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. 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 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. In mathematics, RSA-129 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge. ... A MIPS-year is a measurement of computational steps for computers. ... A gigabyte (derived from the SI prefix giga-) is a unit of information or computer storage equal to one billion (that is, a thousand million) bytes. ... Telcordia Technologies, formerly Bellcore, is an American telecommunications company created in 1984 after the breakup of AT&T. It was split from the original Bell Labs as part of the negotiated consent decree with the US government, and served Research & Development and standards setting functions for the resulting seven Baby... MasPar Computer Corporation was a minisupercomputer vendor that was founded in 1987 by Jeff Kalb. ... In mathematics, RSA-130 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge. ... The RSA numbers, listed by security company RSA Security, are certain large semiprime numbers (i. ...

Implementations

• PPMPQS and PPSIQS
• mpqs
• SIMPQS
• a factoring applet that uses the quadratic sieve if certain conditions are met

• The msieve package for factoring large numbers, written by Jason Papadopoulos, includes a very fast implementation of PPSIQS, very carefully designed for cache-friendliness. It is the fastest available implementation of MPQS, factoring RSA-100 in eleven hours on a 2200MHz Athlon64; on the same system, a 60-digit number takes just over six seconds, a 70-digit number 80 seconds, an 80-digit number just under ten minutes and a 90-digit number about eighty minutes. It is distributed as C source code, with no dependencies for the MPQS and a dependency on the GNU Scientific Library for GNFS; it is written in portable C, though one or two subroutines include x86 assembly language versions. It can be downloaded from the msieve page.

In mathematics, RSA-100 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge. ... This article or section should include material from Athlon The Athlon 64 (codenamed ClawHammer and Newcastle) represents AMDs entry into the consumer 64-bit microprocessor market, released on September 23rd, 2003. ... Code using the library and the computed results In computing, GNU Scientific Library (or GSL) is a software library written in the C programming language for numerical calculations in applied mathematics and science. ...

See also

• UBASIC
• Integer factorization
• Lenstra elliptic curve factorization
• primality test

This article needs to be cleaned up to conform to a higher standard of quality. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves. ... A primality test is an algorithm for determining whether an input number is prime. ...

References

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0-387-94777-9.  Section 6.1: The quadratic sieve factorization method, pp.227–244.

Richard E. Crandall is an American computer scientist who has made contributions to computational number theory. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ...

Other external links

• Reference paper from University of Illinois at Urbana-Champaign
• Quadratic Sieve Algorithm - contains a description of the Shanks-Tonelli algorithm.