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: <478@faron.UUCP>
Date: Tue, 18-Feb-86 19:15:41 EST
Article-I.D.: faron.478
Posted: Tue Feb 18 19:15:41 1986
Date-Received: Wed, 19-Feb-86 08:32:11 EST
References: <5083@stolaf.UUCP> <1404@panda.UUCP> <38@randvax.UUCP>
Distribution: net
Organization: The MITRE Coporation, Bedford, MA
Lines: 43
Xref: linus net.math:2488 net.crypt:513

> In article <1404@panda.UUCP> plw@panda.UUCP (Pete Williamson) writes:
> >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.
> 
> It doesn't, actually.  I know that there are recent results in proving
> that large numbers are prime (rather than "statistically almost certainly
> prime"), but haven't seen anything authoritative that tells who's come
> up with this algorithm, what it's based on, or in fact whether it really
> exists.  Would somebody who would know whether it's been done (like
> David Cantor at UCLA, for example) please post either positive or negative
> *real* information?
> 
> Thanks.
> -- 
> 	Jim Gillogly
> 	{decvax, vortex}!randvax!jim
> 	jim@rand-unix.arpa

The Cohen-Lenstra prime proving algorithm can handily primes up to 200
digits quite readily on most mainframes in about (say) 1/2 hour and 300
digit numbers in several hours. Read their paper in Mathematics of
Computation (1985, I don't recall offhand which issue). In fact it is
possible to do 50% better than their paper describes by a fairly simple
change. The complexity of this algorithm is ln(n) ^ (ln ln ln(n) ).

Shaffi Goldwasser at MIT has turned recent interest in elliptic curves
into a prime proving algorithm that runs in probabilistic polynomial
time but it is not (currently) believed to be practical. It uses a
theorem by Mordell that the group of rational points on an elliptic
curve taken MOD p is finitely generated. We have an O( ln(p)^9) algorithm
due to Schoof for computing the order of the curve MOD p but its
relatively high exponent makes the method impractical. No paper on
Professor Goldwasser's paper has yet appeared (I've requested but not
yet received one).
 
Bob Silverman