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.

- Choose an N you wish to factor.
- Factor N
- Done. (mod details)

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

- Time Analysis: Not yet available
- Source Code: Will have it here soon!
- Alternate Description

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