Quadratic sieve

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. 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. 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, 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 the base of the natural logarithm. Let x mod y denote the remainder after dividing x by y. To factorize the integer n, Fermat's method entails a search for a single number a, n1/2<a<n-1, 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 numbers 32, 115, 200 is a square, but the product (32)(200) = 6400 = 802 is a square. Modulo 1649, this product is (32)(200) = (412)(432) = ((41)(43))2 = 1142 as (41)(43) mod 1649 = 114. The observation that (32)(200) = 802 thus gives a congruence of squares: 1142 ≡ 802 (mod 1649). To finish this factorization example, continue reading Congruence of squares.