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