Quadratic sieve
Encyclopedia
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 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.
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, and hope the least non-negative remainder modulo n is a perfect square
(in the integers). For example, 802 mod 5959 is 441, which is 212. 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
in the L-notation
.
The constant e is usually used as the base of the logarithm.
y denote the remainder after dividing x by y. To factorise the integer n, Fermat's method
entails a search for a single number a such that a2 mod n is a square. But these a are hard to find. The quadratic sieve consists of computing a2 mod n for several a, then finding a subset of these whose product is a square. This will yield a congruence of squares.
For example, 412 mod 1649 = 32, 422 mod 1649 = 115, and 432 mod 1649 is 200. None of these is a square, but the product (32)(200) = 6400 = 802, and mod 1649, (32)(200) = (412)(432) = ((41)(43))2. Since (41)(43) mod 1649 = 114, this is a congruence of squares: 1142 ≡ 802 (mod 1649). To finish this factorization example, continue reading Congruence of squares
.
But how to solve the problem of, given a set of numbers, finding a subset whose product is a square? The solution uses the concept of an exponent vector. For example, the prime-power factorization
of 504 is 23325071. It can be represented by 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). Multiplying the numbers is the same as componentwise adding their exponent vectors: (504)(490) has the vector (4,2,1,3).
A number is a square if 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), so (56)(126) is a square. Searching for a square requires knowledge only of the parity of the numbers in the vectors, so it is possible to 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.
The problem is reduced to: given a set of (0,1)-vectors, find a subset which adds to the zero vector mod 2. This is a linear algebra
problem; the solution is a linear dependency. It is a theorem of linear algebra that with more vectors than each vector has elements, such a dependency must exist. It can be found efficiently, for example by placing the vectors as rows in a matrix
and then using Gaussian elimination
, which is easily adapted to work for integers mod 2 instead of real number
s. The desired square is then the product of the numbers corresponding to those vectors.
However, simply squaring many random numbers mod n produces a very large number of different prime factors, and so very long vectors and a very large matrix. The answer is to look specifically for numbers a such that a2 mod n has only small prime factors (they are smooth number
s). 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 remainder of this article explains details and extensions of this basic algorithm.
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 x 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.
Multiply these together:
and multiply both sides by (11−1)2 modulo 91. 11−1 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.
, although this increases the running time for the data collection phase. Another method that has some acceptance is the elliptic curve method
. The elliptic curve method is commonly referred to simply as "ECM" within the vernacular of number theory. However, in practice, a process called sieving is used.
Thus solving y(x) ≡ 0 (mod p) for x generates a whole sequence of ys 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 the square of a factor-base prime.
At the end of the factor base, any A[] containing a value above a threshold of roughly log(n) 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 (trial division by small primes, SQUFOF, Pollard rho, and ECM are usually used in some combination) for factoring a number known to have only small factors.
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.
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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
(QS) is a modern integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithm and, in practice, the second fastest method known (after the general number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
). 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
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
to be factored, and not on special structure or properties. It was invented by Carl Pomerance
Carl Pomerance
Carl Bernard Pomerance is a well-known number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number has at least 7 distinct prime factors. He immediately joined the faculty at the...
in 1981 as an improvement to Schroeppel's linear sieve.
Basic aim
The algorithm attempts to set up a congruence of squaresCongruence of squares
In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.-Derivation:Given a positive integer n, Fermat's factorization method relies on finding numbers x, y satisfying the equality...
modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
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
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
and solves it to obtain a congruence of squares. The data collection phase can be easily parallelized
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
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
Block Wiedemann algorithm
The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalisation of an algorithm due to Don Coppersmith.- Coppersmith's 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, and hope the least non-negative remainder modulo n is a perfect square
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
(in the integers). For example, 802 mod 5959 is 441, which is 212. 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
Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:N = a^2 - b^2.\...
.
The quadratic sieve is a modification of Dixon's factorization method
Dixon's factorization method
In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which a run-time bound not reliant on conjectures about the smoothness properties of values of a polynomial is...
.
The general running time required for the quadratic sieve (to factor an integer n) is
in the L-notation
L-notation
L-notation is an asymptotic notation analogous to big-O notation, denoted as L_n[\alpha,c] for a bound variable n tending to infinity. Like big-O notation, it is usually used to roughly convey the computational complexity of a particular algorithm....
.
The constant e is usually used as the base of the logarithm.
The approach
Let x modModular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
y denote the remainder after dividing x by y. To factorise the integer n, Fermat's method
Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:N = a^2 - b^2.\...
entails a search for a single number a such that a2 mod n is a square. But these a are hard to find. The quadratic sieve consists of computing a2 mod n for several a, then finding a subset of these whose product is a square. This will yield a congruence of squares.
For example, 412 mod 1649 = 32, 422 mod 1649 = 115, and 432 mod 1649 is 200. None of these is a square, but the product (32)(200) = 6400 = 802, and mod 1649, (32)(200) = (412)(432) = ((41)(43))2. Since (41)(43) mod 1649 = 114, this is a congruence of squares: 1142 ≡ 802 (mod 1649). To finish this factorization example, continue reading Congruence of squares
Congruence of squares
In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.-Derivation:Given a positive integer n, Fermat's factorization method relies on finding numbers x, y satisfying the equality...
.
But how to solve the problem of, given a set of numbers, finding a subset whose product is a square? The solution uses the concept of an exponent vector. For example, the prime-power factorization
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
of 504 is 23325071. It can be represented by 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). Multiplying the numbers is the same as componentwise adding their exponent vectors: (504)(490) has the vector (4,2,1,3).
A number is a square if 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), so (56)(126) is a square. Searching for a square requires knowledge only of the parity of the numbers in the vectors, so it is possible to 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.
The problem is reduced to: given a set of (0,1)-vectors, find a subset which adds to the zero vector mod 2. This is a linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
problem; the solution is a linear dependency. It is a theorem of linear algebra that with more vectors than each vector has elements, such a dependency must exist. It can be found efficiently, for example by placing the vectors as rows in a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
and then using Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
, which is easily adapted to work for integers mod 2 instead of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. The desired square is then the product of the numbers corresponding to those vectors.
However, simply squaring many random numbers mod n produces a very large number of different prime factors, and so very long vectors and a very large matrix. The answer is to look specifically for numbers a such that a2 mod n has only small prime factors (they are smooth number
Smooth number
In number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
s). 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
Sieve theory
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 primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
, discussed later, from which the algorithm takes its name.
The algorithm
To summarize, the basic quadratic sieve algorithm has these main steps:- 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.
- Use sieving to locate π(B) + 1 numbers ai such that bi=(ai2 mod n) is B-smooth.
- Factor the bi and generate exponent vectors mod 2 for each one.
- Use linear algebra to find a subset of these vectors which add to the zero vector. Multiply the corresponding ai together naming the result mod n: a and the bi together which yields a B-smooth square b2.
- 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.
- 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 x2 ≡ y2 (mod n). It selects a set of primesPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
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 x 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 (11−1)2 modulo 91. 11−1 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 divisionTrial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
, although this increases the running time for the data collection phase. Another method that has some acceptance is the elliptic curve method
Lenstra elliptic curve factorization
The Lenstra elliptic curve factorization or the elliptic curve factorization method is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method...
. The elliptic curve method is commonly referred to simply as "ECM" within the vernacular of number theory. However, in practice, a process called sieving is used.
Thus solving y(x) ≡ 0 (mod p) for x generates a whole sequence of ys 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
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
.)
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 the square of a factor-base prime.
At the end of the factor base, any A[] containing a value above a threshold of roughly log(n) 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 (trial division by small primes, SQUFOF, Pollard rho, and ECM are usually used in some combination) for factoring a number known to have only small factors.
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 4 primes are necessary. The first 4 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 equationto 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 + 124 Y factors 124 29 20 • 170 • 230 • 291 127 782 21 • 171 • 231 • 290 195 22678 21 • 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 methodDixon's factorization methodIn number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which a run-time bound not reliant on conjectures about the smoothness properties of values of a polynomial is...
.
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 3 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 divisionTrial divisionTrial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
or Pollard rho could have found a factor with much less computation.
Multiple polynomials
In practice, many different polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s are used for y, since only one polynomial will not typically provide 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) = x2 − n:
Assuming
is a multiple of A, so that 
the polynomial y(x) can be written as 
. If then A is a square, only the factor 
has to be considered.
This approach (called MPQS, Multiple Polynomial Quadratic Sieve) is ideally suited for parallelizationParallel algorithmIn computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
, since each processorCentral processing unitThe central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
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.
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 semiprimeSemiprimeIn mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....
, producing the follow parameters:
- Trial factoring cutoff: 27 bits
- Sieve interval (per polynomial): 393216 (12 blocks of size 32768)
- Smoothness bound: 1300967 (50294 primes)
- Number of factors for polynomial A coefficients: 10 (see Multiple polynomials above)
- Large prime bound: 128795733 (26 bits) (see Large primes above)
- Smooth values found: 25952 by sieving directly, 24462 by combining numbers with large primes
- Final matrix size: 50294 × 50414, reduced by filtering to 35750 × 35862
- Nontrivial dependencies found: 15
- Total time (on a 1.6 GHz UltraSparc III): 35 min 39 seconds
- Maximum memory used: 8 MB
Factoring records
Until the discovery of the number field sieveGeneral number field sieveIn number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
(NFS), QS was the asymptotically-fastest known general-purpose factoring algorithm. Now, Lenstra elliptic curve factorizationLenstra elliptic curve factorizationThe Lenstra elliptic curve factorization or the elliptic curve factorization method is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method...
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. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 MIPS-yearMIPS-yearA MIPS-year is a measurement of computational steps for computers. MIPS means million instructions per second, and a MIPS-year is equal to the number of steps processed for one year at one million instructions per second....
s, done in distributed fashion over the Internet. The data collected totaled 2GBGigabyteThe gigabyte is a multiple of the unit byte for digital information storage. The prefix giga means 109 in the International System of Units , therefore 1 gigabyte is...
. The data processing phase took 45 hours on Bellcore's (now Telcordia TechnologiesTelcordia TechnologiesTelcordia Technologies, formerly Bell Communications Research, Inc. or Bellcore, is a telecommunications research and development company based in the United States created as part of the 1982 Modification of Final Judgment that broke up American Telephone & Telegraph...
) MasParMasParMasPar Computer Corporation was a minisupercomputer vendor that was founded in 1987 by Jeff Kalb. The company was based in Sunnyvale, California....
(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 record is a 135-digit cofactor of
, itself an Aurifeuillian factor of 
, which was split into 66-digit and 69-digit prime factors in 2001.
Implementations
- PPMPQS and PPSIQS
- mpqs
- SIMPQS is a fast implementation of the self initialising multiple polynomial quadratic sieve written by William Hart. It provides support for the large prime variant and uses Jason Papadopoulos' block Lanczos code for the linear algebra stage. SIMPQS is accessible as the qsieve command in the SAGE computer algebra package or can be downloaded in source form. SIMPQS is optimized for use on Athlon and Opteron machines, but will operate on most common 32 and 64 bit architectures. It is written entirely in C.
- a factoring applet by Dario Alpern, that uses the quadratic sieve if certain conditions are met.
- The PARI/GPPARI/GPPARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
computer algebra package includes an implementation of the self initialising multiple polynomial quadratic sieve implementing the large prime variant. It was adapted by Thomas Papanikolaou and Xavier Roblot from a sieve written for the LiDIA project. The self initialisation scheme is based on an idea from the thesis of Thomas Sosnowski. - A variant of the quadratic sieve is available in the MAGMAMagma computer algebra systemMagma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma...
computer algebra package. It is based on an implementation of Arjen Lenstra from 1995, used in his "factoring by email" program. - msieve, an implementation of the multiple polynomial quadratic sieve with support for single and double large primes, written by Jason Papadopoulos. Source code and a Windows binary are available.
- YAFU, written by Ben Buhrow, is similar to msieve but is faster for most modern processors. It uses Jason Papadopoulos' block Lanczos code. Source code and binaries for Windows and Linux are available.
- Ariel, a simple Java implementation of the quadratic sieve for didactic purposes.
Other external links
- Reference paper from University of Illinois at Urbana-ChampaignUniversity of Illinois at Urbana-ChampaignThe University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
-
-
-
