Newsgroups: sci.math
From: pmontgom@cwi.nl (Peter L. Montgomery)
Subject: Re: What is the difference between QS and MPQS?
Date: Tue, 10 Mar 1998 10:19:20 GMT

In article <35011AD2.834D12A4@welty.netkonect.co.uk> 
Chris Welty <welty@welty.netkonect.co.uk> writes:
>How does the Multiple Polynomial Quadratic Sieve differ from the
>Quadratic Sieve?
>I have cleverly deduced that it uses more than one polynomial, but which
>polynomials are used?

	Suppose we want to factor an integer N.
Simple QS uses one polynomial f(x) = (x + x0)^2 - N
where x0 = round(sqrt(N)).
When x is small (in absolute value), this is approximately 
2*x*x0  (the value of x0^2 - N is at most x0, and x^2 is small).
If we try R values of x, from -R/2 to R/2, the largest
residue has absolute value about R*x0 or R*sqrt(N).

       Multiple polynomial quadratic sieve (MPQS) uses
many polynomials f(x) = A x^2 + Bx + C.
In the simplest case, A is a perfect square and B^2 - 4AC = N.  
If a residue f(x) factors nicely, then

	4A f(x) = (2Ax + B)^2 - (B^2 - 4AC) = (2Ax + B)^2 - N

This f(x) has a known square root modulo N, and can be saved for later use.

        If we want x to range from -R/2 to R/2,
we try to choose coefficients so f(R/2) = f(-R/2) = -f(0).
That is, we want approximately,

           A ~= sqrt(2N)/R
           B ~= 0
           C ~= -R sqrt(2N)/8

The polynomial is approximately sqrt(2N) * (x^2  - R^2/8) / R
The largest value for x in [-R/2, R/2] is R*sqrt(2N)/8.

         The advantage to MPQS is that one can generate many
(A, B, C) pairs, and switch polynomials when the residues grow too large.
Residues from different polynomials can be merged later.
It is suitable for parallel processing, if each processor
has its own polynomials.
If N == 1 (mod 4), choose a prime a near our desired value for sqrt(A)
and such that N is a quadratic residue mod a.  Let A = a^2.  
We can solve B^2 - 4a^2C = N by first choosing B mod a, then B mod a^2, 
and possibly  replacing B by a^2 - B to make B odd.
Now let C be the integer (B^2 - N)/4a^2.

        When N == 3 (mod 4), this gives a half-integer for C,
and the polynomial must be doubled.  Its discriminant will be 4N rather than N.

	Robert Silverman describes MPQS in Mathematics of Computation, 
January, 1987.

-- 
        Peter-Lawrence.Montgomery@cwi.nl    San Rafael, California

Q: Why will historians view El Nino as a dignitary?
A (backwards): .gnikaerb sdnuorg yreve ta tneserp neeb sah ti esuaceB