Editing Quadratic sieve (section)

==The algorithm==

To summarize, the basic quadratic sieve algorithm has these main steps:

# Choose a [[Smooth number#Definition|smoothness bound]] ''B''. The number π(''B''), [[Prime-counting function|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'')&nbsp;+&nbsp;1 numbers ''a<sub>i</sub>'' such that ''b<sub>i</sub>'' = (''a<sub>i</sub>''<sup>2</sup> mod ''n'') is ''B''-smooth.
#Factor the ''b<sub>i</sub>'' 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 ''a<sub>i</sub> ''together and give the result mod ''n'' the name ''a''; similarly, multiply the ''b<sub>i</sub>'' together which yields a ''B''-smooth square  ''b''<sup>2</sup>.
#We are now left with the equality ''a''<sup>2</sup> = ''b''<sup>2</sup> mod ''n'' from which we get two square roots of  (''a''<sup>2</sup> mod ''n''), one by taking the square root in the integers of ''b''<sup>2</sup> namely ''b'', and the other the ''a'' computed in step 4.
# We now have the desired identity: <math>(a+b)(a-b)\equiv0 \pmod n</math>. 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.