Editing Quadratic sieve (section)

==Multiple polynomials==
In practice, many different [[polynomial]]s are used for ''y'' so that when ''y''(''x'') starts to become large, resulting in poor density of smooth ''y'', this growth can be reset by switching polynomials. As usual, we choose ''y''(''x'') to be a square modulo ''n'', but now with the form

<math display=block>y(x)=(Ax+B)^2-n \qquad A,B\in\mathbb{Z}.</math>

<math>B</math> is chosen such that <math>B^2 = n \pmod A</math>, so <math>B^2 - n = AC</math> for some <math>C</math>. The polynomial y(x) can then be written as <math>y(x) = A\cdot(Ax^2 + 2Bx + C)</math>. If ''A'' is a square or a smooth number, then only the factor <math>(Ax^2 + 2Bx + C)</math> has to be checked for smoothness.

This approach, called Multiple Polynomial Quadratic Sieve (MPQS), is ideally suited for [[parallel algorithm|parallelization]], since each [[central processing unit|processor]] involved in the factorization can be given ''n'', the factor base and a collection of polynomials, and it will have no need to communicate with the central processor until it has finished sieving with its polynomials.