BACKGROUND
This method was written in 1985 by H.W. Lenstra Jr.

BIG IDEA
This method is very similar to Pollardīs P-1 method. In fact, it *is*
Pollardīs P-1 method, except instead of the * operation (as used in
Pollardīs `a`^`k` calculation) I use "some other" operation.
What is this operation? Well, that will take a bit of explaining...
but the principle is identical: Pick a number (point). Raise it to a
power (iterate it a few times). This `will` be equal to one (it
will lie in the Kernel of a homomorphism). This means that `p` divides
`a`^`k`-1 (This means that a coordinate of this point will be
equal to 0 (mod `p`). Easy! Will explain more later...

METHOD
- Choose a number,
`N`, you wish to factor

TECHNICAL ANALYSIS
- Theoretical Runtime:
- O( exp(sqrt( ln(n)*ln(ln(n)) )) ) ...meaning, "not bad."

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