BACKGROUND
Developed in 1987 by Robert D. Silverman based on a method by Carl
Pomerance.
BIG IDEA
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.
METHOD
- Choose an N you wish to factor.
- Factor N
- Done. (mod details)
TECHNICAL ANALYSIS
- Theoretical Runtime:
- O( exp( sqrt(ln(n)*ln(ln(n)))) )
LINKS
Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page
Paul Herman
pherman@frenchfries.net
Last Updated: May 23, 1997