Multiple Polynomials
In practice, many different polynomials are used for y, since only one polynomial will not typically provide enough (x, y) pairs that are smooth over the factor base. The polynomials used must have a special form, since they need to be squares modulo n. The polynomials must all have a similar form to the original y(x) = x2 − n:
Assuming is a multiple of A, so that the polynomial y(x) can be written as . If then A is a square, only the factor has to be considered.
This approach (called MPQS, Multiple Polynomial Quadratic Sieve) is ideally suited for parallelization, since each 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 is finished with its polynomials.
Read more about this topic: Quadratic Sieve
Famous quotes containing the word multiple:
“... the generation of the 20’s was truly secular in that it still knew its theology and its varieties of religious experience. We are post-secular, inventing new faiths, without any sense of organizing truths. The truths we accept are so multiple that honesty becomes little more than a strategy by which you manage your tendencies toward duplicity.”
—Ann Douglas (b. 1942)