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

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...
  1. Choose a number, N, you wish to factor

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


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 23, 1997