🚀 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 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.