Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ulysses.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!smb
From: smb@ulysses.UUCP (Steven Bellovin)
Newsgroups: net.math,net.crypt
Subject: faster factoring method found
Message-ID: <10019@ulysses.UUCP>
Date: Tue, 12-Mar-85 08:44:29 EST
Article-I.D.: ulysses.10019
Posted: Tue Mar 12 08:44:29 1985
Date-Received: Wed, 13-Mar-85 00:41:45 EST
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 8
Xref: watmath net.math:1896 net.crypt:303

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.