Developed in 1987 by Robert D. Silverman based on a method by Carl Pomerance.

So you want to factor N, eh? Well, just like in Dixon's Algorithm, we are looking for x and y such that:
x^2 = y^2 (mod N)
We want to look for quadratic residues (numbers which are squares mod N) which can be factored into only small primes. So, we choose a random r, like sqrt(N)+k, k=1, 2, 3,... and look for factors, p, such that:
N=r^2 (mod p)
Again, we only want to check p's, such that N is a quadratic residue mod p. (We can find this with the help of a certain generating polynomial.) The set of these small primes for which this is true is called the "Factor Base".

Next, the congruences, x^2 = N (mod p) needs to be solved for each p in the "Factor Base".

Next, a sieve is applied (using only primes in the Factor Base) to find out which r^2 - N can be factored, for each r.

Gaussian Elimination is then used (as in Dixon's method) to find a product of the (r^2 - N)'s yielding a perfect square.

Note: The use of multiple polynomials gives a better chance of factorization, requires a shorter sieve interval, and is well suited to parallel processing.

It doesn't make perfect sense to me yet, but as soon as I work out the details, I'll post them here.

  1. Choose an N you wish to factor.
  2. Factor N
  3. Done. (mod details)

Theoretical Runtime:
O( exp( sqrt(ln(n)*ln(ln(n)))) )


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 23, 1997