Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 SMI; site sun.uucp
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!decwrl!sun!falk
From: falk@sun.uucp (Ed Falk)
Newsgroups: net.math,net.crypt
Subject: Re: factoring algorithms and RSA public key code
Message-ID: <3257@sun.uucp>
Date: Wed, 19-Feb-86 21:44:34 EST
Article-I.D.: sun.3257
Posted: Wed Feb 19 21:44:34 1986
Date-Received: Fri, 21-Feb-86 05:31:32 EST
Distribution: net
Organization: Sun Microsystems, Inc.
Lines: 24
Xref: watmath net.math:2867 net.crypt:552

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

If I remember correctly, the original RSA paper published by
MIT asserted that proving whether or not a number is prime doesn't
help you at all to factor one that isn't.  I realize that that
paper is out of date now, but I also remember that an earlier
posting by Bob mentioned that the current record for factoring
was a 71 digit number in 9.5 hours and that he expected that
current state-of-the-art technology and the latest algorithms
might be able to factor a 100-digit number in 1 or 2 months.

I haven't got a calculator handy, but I suspect that
O(exp(sqrt(ln(n) * ln(ln(n))))) is probably a lot larger for
a 200-digit number than for a 100-digit number.

ed falk