Editing Quadratic sieve (section)

== The approach ==

To factorize the integer ''n'', [[Fermat's factorization method|Fermat's method]] entails a search for a single number ''a'', {{math|''n''<sup>1/2</sup> < ''a'' < ''n''−1}}, such that the remainder of ''a''<sup>2</sup> divided by ''n'' is a square. But these ''a'' are hard to find. The quadratic sieve consists of computing the remainder of ''a''<sup>2</sup>/''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: <math>41^2 \equiv 32, 42^2 \equiv 115, 43^2 \equiv 200 \pmod{1649}</math>. None of the integers <math>32, 115, 200</math> is a square, but the product <math>32 \cdot 200 = 80^2</math> is a square. We also had 
:<math>32 \cdot 200 \equiv 41^2 \cdot 43^2 = (41 \cdot 43)^2 \equiv 114^2 \pmod{1649}</math>
since <math>41 \cdot 43 \equiv 114 \pmod{1649}</math>.
The observation that <math>32 \cdot 200 = 80^2</math> thus gives a [[congruence of squares]] 
:<math>114^2 \equiv 80^2 \pmod{1649}.</math> 
Hence <math>114^2 - 80^2 = (114 + 80) \cdot (114 - 80) = 194 \cdot 34 = k \cdot 1649</math> for some integer <math>k</math>. We can then factor 
:<math> 1649 = \gcd( 194, 1649 ) \cdot \gcd( 34, 1649 ) = 97 \cdot 17</math>
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 power]]s. We do this in a vector format; for example, the prime-power factorization of 504 is 2<sup>3</sup>3<sup>2</sup>5<sup>0</sup>7<sup>1</sup>, 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 (mathematics)|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 (mathematics)|ring]] <math>\mathbb{Z}/2\mathbb{Z}</math> 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 [[Rank–nullity theorem|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 number|prime]] factors, and thus very long vectors and a very large matrix. The trick is to look specifically  for numbers ''a'' such that ''a''<sup>2</sup> 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 [[sieve theory|sieving]], discussed later, from which the algorithm takes its name.