Loading ...
Sorry, an error occurred while loading the content.

The Multiple Polynomial Quadratic Sieve

Expand Messages
  • Kermit Rose
    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 8:49 PM
    • 0 Attachment
      Hello Prime number friends.

      I found the following to be very interesting and informative.


      The Multiple Polynomial Quadratic Sieve

      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.

      The Quadratic sieve just described generates a set of quadratic
      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.