Editing Quadratic sieve (section)

==How QS optimizes finding congruences==
The quadratic sieve attempts to find pairs of integers ''x'' and ''y''(''x'') (where ''y''(''x'') is a function of ''x'') satisfying a much weaker condition than ''x''<sup>2</sup> ≡ ''y''<sup>2</sup> (mod ''n''). It selects a set of [[prime number|primes]] called the ''factor base'', and attempts to find ''x'' such that the least absolute remainder of ''y''(''x'') = ''x''<sup>2</sup> mod ''n'' factorizes completely over the factor base. Such ''y'' values are said to be ''smooth'' with respect to the factor base.

The factorization of a value of ''y''(''x'') that splits over the factor base, together with the value of ''x'', is known as a ''relation''. The quadratic sieve speeds up the process of finding relations by taking ''x'' close to the square root of ''n''. This ensures that ''y''(''x'') will be smaller, and thus have a greater chance of being smooth.

:<math>y(x)=\left(\left\lceil\sqrt{n}\right\rceil+x\right)^2-n\hbox{ (where }x\hbox{ is a small integer)}</math>
:<math>y(x)\approx 2x\left\lceil\sqrt{n}\right\rceil</math>

This implies that ''y'' is on the order of 2''x''[{{radic|''n''}}]. However, it also implies that ''y'' grows linearly with ''x'' times the square root of ''n''.

Another way to increase the chance of smoothness is by simply increasing the size of the factor base.  However, it is necessary to find at least one smooth relation more than the number of primes in the factor base, to ensure the existence of a linear dependency.

===Partial relations and cycles===
Even if for some relation ''y''(''x'') is not smooth, it may be possible to merge two of these ''partial relations'' to form a full one, if the two ''y''{{'}}s are products of the same prime(s) outside the factor base. [Note that this is equivalent to extending the factor base.] For example, if the factor base is {2, 3, 5, 7} and ''n'' = 91, there are partial relations:

:<math>{21^2\equiv 7^1\cdot 11\pmod{91}}</math>
:<math>{29^2\equiv 2^1\cdot 11\pmod{91}}</math>

Multiply these together:

:<math>{(21\cdot 29)^2\equiv2^1\cdot7^1\cdot11^2\pmod{91}}</math>

and multiply both sides by (11<sup>&minus;1</sup>)<sup>2</sup> modulo 91. 11<sup>&minus;1</sup> modulo 91 is 58, so:

:<math>(58\cdot 21\cdot 29)^2\equiv 2^1\cdot7^1\pmod{91}</math>
:<math>14^2\equiv 2^1\cdot7^1\pmod{91}</math>

producing a full relation. Such a full relation (obtained by combining partial relations) is called a ''cycle''. Sometimes, forming a cycle from two partial relations leads directly to a congruence of squares, but rarely.

===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.