agr@vaxine.UUCP (02/02/87)
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.
bs@linus.UUCP (02/04/87)
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
pmontgom@sdcrdcf.UUCP (02/05/87)
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 elliptic curve. Lenstra discovered this method (ECM) in February, 1985. An article "Speeding the Pollard and Elliptic Curve Methods of Factorization" by me in the latest (January, 1987) Mathematics of Computation describes the algorithm and how I implement it. ECM is probabilistic, since random parameters must be selected to get the elliptic curve and hence the precise value of p-t. Only a few trials are needed to get a factor up to 15 digits, and 30 trials will find most factors below 20 digits. All arithmetic is done modulo the number one is attempting to factor, so it can be tried on arbitrary-sized inputs. My most successful result has been the 36-digit factor 227693725298545340302283668318476481 of the Lucas number L464. Its previous cofactor was 94 digits, and this is the largest number successfully factored into two non-algebraic factors both larger than its cube root. By the way, that issue of Mathematics of Computation is dedicated to Daniel Shanks. -- Peter Montgomery {aero,allegra,bmcg,burdvax,hplabs,ihnp4, psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom Don't blame me for the crowded freeways - I don't drive.