🚀 go-pugleaf

In article <408@vaxine.UUCP>, agr@vaxine.UUCP (Arnold Reinhold) writes:
> 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.


This algorithm is not new. It first came to light around 1985.
 It uses the fact that an additive group
exists on elliptic curves taken mod p. A theorem of Mordell says the
group is finitely generated. A theorem due to Hasse (Riemann Hypothesis
for finite fields) says that the order of the group is bounded by
[p-2sqrt(p)-1 , p + 2sqrt(p)+1].

A further theorem says that for each value in this interval there does
exist some corresponding elliptic curve. It is hoped, by choosing a
random elliptic curve that the order of its group will have only
small prime factors. By doing the computations mod N, rather than
mod p one actually works in a finite ring, rather than group.
Doing the group addition operation requires taking a multiplicative
inverse. One starts with a point P on the curve and computes
successively:

2P
3(2P)
5(3(2P))  etc.
 
Eventually one cannot do the required inversion to add points because
the inverse doesn't exist (remember we are working mod N, i.e. in a ring
not a group) Then by taking a GCD with N one can find the factor p.

Peter Montgomery and myself have factored 100's of very large numbers
using this method. Richard Brent has also contributed factors.
 
Please don't flood me with requests for the program.
 
Bob Silverman