This algorithm uses residues (or "the remainder modulo N") from the integer sqrt() function, just like in Fermat's method. A way to find integer square roots is to use continued fractions.

This was the fastest algorithm before the Quadratic Sieve method took over.

- Choose the number,
`N`, you wish to factor - Factor
`N` - Done! (mod details)

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

- Time Analysis: Not yet available
- Source Code: Not yet available
- 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