🚀 go-pugleaf

A news article in Nature (15 Jan 1987, p199) describes a new method for
factoring integers devised by Hendrik Lenstra.  It apparently generalizes the
"p-1 method" to p-t, where t ranges over a set of values depending on a choice
of eliptic curve.

"Provided there is a reasonably dense set of numbers near p that are a product
of small primes, the method will find a factor rapidly.  The precise running
time is rather complicated, and its proof depends on a plausable but unproved
conjecture on this density.  Other known methods have a similar conjectured
running time, but they lack one important feature of Lenstra's method: the
running time depends on the size of the prime factors of N."

As the article points out: "...nobody has ever proved that prime factorization
really must be as hard as it seems to be.  Efficient and effective methods have
not been ruled out."  Caveat cryptor.