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.
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, 80 2 ≡ 441 = 21 2 ( mod 5959 ) {\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}} . 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
e ( 1 + o ( 1 ) ) ln n ln ln n = L n [ 1 / 2 , 1 ] {\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}
in the L-notation. 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: 41 2 ≡ 32 , 42 2 ≡ 115 , 43 2 ≡ 200 ( mod 1649 ) {\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}} . None of the integers 32 , 115 , 200 {\displaystyle 32,115,200} is a square, but the product 32 ⋅ 200 = 80 2 {\displaystyle 32\cdot 200=80^{2}} is a square. We also had
32 ⋅ 200 ≡ 41 2 ⋅ 43 2 = ( 41 ⋅ 43 ) 2 ≡ 114 2 ( mod 1649 ) {\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}
since 41 ⋅ 43 ≡ 114 ( mod 1649 ) {\displaystyle 41\cdot 43\equiv 114{\pmod {1649}}} . The observation that 32 ⋅ 200 = 80 2 {\displaystyle 32\cdot 200=80^{2}} thus gives a congruence of squares
114 2 ≡ 80 2 ( mod 1649 ) . {\displaystyle 114^{2}\equiv 80^{2}{\pmod {1649}}.}
Hence 114 2 − 80 2 = ( 114 + 80 ) ⋅ ( 114 − 80 ) = 194 ⋅ 34 = k ⋅ 1649 {\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649} for some integer k {\displaystyle k} . We can then factor
… excerpt ends here. Continue reading the full article.
