Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site faron.UUCP
Path: utzoo!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math,net.crypt
Subject: Re: factoring algorithms and RSA public key code
Message-ID: <476@faron.UUCP>
Date: Thu, 13-Feb-86 23:23:00 EST
Article-I.D.: faron.476
Posted: Thu Feb 13 23:23:00 1986
Date-Received: Fri, 14-Feb-86 07:35:20 EST
References: <5083@stolaf.UUCP> <1404@panda.UUCP>
Distribution: net
Organization: The MITRE Coporation, Bedford, MA
Lines: 63
Xref: linus net.math:2472 net.crypt:496

> >
> >I just gave my senior comps talk on the RSA public key
> >cipher, and after my talk, someone mentioned reading about
> >a new factoring algorithm which is very efficient (i.e.
> >much better than O(exp(sqrt(ln(n)*ln(ln(n)))))).
> >
> >This, of course, would have devastating implications for
> >the security of the RSA code.  Anybody else know about this?
> >I think the person told me it had been developed by someone
> >at MIT.
> >
> 
> I recently heard (second hand) that RSA has been rendered effectively
> useless due to an advance in the strategy of factoring large numbers.
> Apparently the general factoring problem remains "difficult", but
> factoring large numbers that contain large prime factors is now provably
> "easy".  I believe that the advance comes from MIT but I do not know
> who the researchers are.  The National Security Agency also has known
> about this for some time, I have heard.
> 
> Hope this helps.
> 
> 
> -- 
> 						Pete Williamson
> "By hook or by crook, we will !!" ... #2

Let me throw water on this nonsense before it goes any further. 
This information is first hand, not rumor or second hand.

I currently possess the fastest factoring algorithm in the world today.
I am in constant contact with the many researchers doing work on factoring
and primality testing. 

The fastest known algorithms, of which there are several, all have 
complexity function: L(n) = exp( sqrt( ln(n) lnln(n))). Lenstra's
elliptic curve algorithm, since it finds small factors first actually
does better than this, on average, but still has the same worst case.
The fastest algorithm for factoring a number which is the product of
two nearly equal primes is a modification of Pomerance's Quadratic
Sieve. The current record for factoring a number with two large prime
factors is the 71 digit number (10^71-1)/9. It was done in 9.5 hours
on a CRAY XMP in 1984 by a group of mathematicians at Sandia Labs.

I anticipate announcing to the net in the next couple of days a new
record, accomplished with an improved version of the algorithm running
on a VAX!. It is a 75 digit cofactor of 6^128 + 1. Despite this, 100 digit 
numbers are still beyond practical reach. Maybe 10 CRAY 2's could do  a 100 
digit number in 1 or two months.
 
I am publishing a paper on the implementation of the improved algorithm
in "Mathematics of Computation". I'll be happy to provide pre-prints
for those SERIOUSLY interested but please keep in mind that I can't
handle too many requests. Just send me your US mail address.
 

I have checked this rumor about a new algorithm with people at MIT and
with others. Perhaps you are mistaking Shaffi Goldwasser's new primality
test which uses elliptic curves with a factoring algorithm. Her new
method runs in random polynomial time except for all but a few abnormal
cases.
 
Bob Silverman