smb@ulysses.UUCP (Steven Bellovin) (03/12/85)
The latest "Science News" (3/9/85) reports that Hendrik Lenstra has found a new fast factoring method. They don't give any details, other than to say it depends on elliptic curves of the form y^2 = x^3 + ax + b, where a and b are random, and that one implementation is only about 250 lines of C. It's best at factoring numbers that are the product of three or more primes, or two primes that are "far apart in value". For numbers that are the product of two relatively close primes, Lenstra's new algorithm appears to be comparable with Carl Pomerance's quadratic seive.