## The Multiple Polynomial Quadratic Sieve

Expand Messages
• Hello Prime number friends. I found the following to be very interesting and informative. The Multiple Polynomial Quadratic Sieve I Quote (slightly modified)
Message 1 of 1 , Aug 18, 2010
Hello Prime number friends.

I found the following to be very interesting and informative.

I Quote (slightly modified) from page 207 of "Prime Numbers
and Computer Methods for Factorization", copyright 1994,
BirkHauser,

by Hans Riesel,
Department of mathematics,
The Royal Institute of Technology,
S-100 44
Stockholm, Sweden.

residues mod N, factorisable within the factor base from a single
polynomial Q(x) = ( int(sqrt(N)) + x)**2 - N = t**2 - N.

Since smooth numbers are not common, we have to do a lot of
sieving before the necessary number of easily factored square
residues are found. This leads to much sieving for large values
of x, which is costly.

This problem is coped with by the following idea of Peter
Montgomery. In t**2 - N, replace t with a t + b,
where a and b are integers satisfying b**2 = N mod a,
and
-a/2 =< b =< a/2.

The resulting polynomial (at + b)**2 - N
= a(at**2 + 2 b t ) + (b**2 - N)
will have all of its values divisible by a. If a is also a known
square residue mod N, we need only find the smooth values of

(1/a) ( (a t + b)**2 - N) = a t**2 + 2 b t + (b**2 - N)/a.

Since there are many choices for a and b, each polynomial used
can be run for values of t between much small limits than with
the simple quadratic sieve using only one polynomial, and we can
still find the necessary number of smooth quadratic residues
mod N.

Given Reference:

R. D. Silverman, "The Multiple Polynomial Quadratic Sieve"
Math COmp 48 (1987) pp 329-339
Your message has been successfully submitted and would be delivered to recipients shortly.