Editing Quadratic sieve (section)

===Checking smoothness by sieving===
There are several ways to check for smoothness of the ''y''s. The most obvious is by [[trial division]], although this increases the running time for the data collection phase. Another method that has some acceptance is the [[Lenstra elliptic curve factorization|elliptic curve method]] (ECM). In practice, a process called ''sieving'' is typically used. If ''f''(''x'') is the [[polynomial]] <math>f(x)=x^2-n</math> we have

:<math>\begin{align}
f(x)&=x^2-n \\
f(x+kp) &= (x+kp)^2-n \\
&= x^2+2xkp+(kp)^2-n \\
&= f(x)+2xkp+(kp)^2\equiv f(x)\pmod{p}
\end{align}</math>

Thus solving ''f(x)'' ≡ 0 (mod ''p'') for ''x'' generates a whole sequence of numbers ''y'' for which ''y''=''f''(''x''), all of which are divisible by ''p''. This is finding a square root modulo a prime, for which there exist efficient algorithms, such as the [[Shanks&ndash;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&nbsp;''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''&nbsp;+&nbsp;''α''] and ''A''[''kp''&nbsp;+&nbsp;''β''].  It is also necessary to solve the quadratic equation modulo small powers of ''p'' in order to recognise numbers divisible by small powers of a factor-base prime.

At the end of the factor base, any ''A''[] containing a value above a threshold of roughly log(''x''<sup>2</sup>−''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 for factoring a number known to have only small factors, such as trial division by small primes, [[SQUFOF]], [[Pollard rho]], and ECM, which are usually used in some combination.

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.