flackc@stolaf.UUCP (Chap Flack) (02/10/86)
*** ERCYNPR GUVF YVAR JVGU LBHE ZRFFNTR *** 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.
flackc@stolaf.UUCP (Chap Flack) (02/10/86)
For whatever reason, my last posting appeared without my .signature and with the wrong ORGANIZATION. Until I get this figured out (and, indeed, thereafter) I am (Chap Flack @ Carleton College, Northfield, MN) --------------------- Chap Flack ihnp4!stolaf!agnes!flackc Carleton College ihnp4!stolaf!flackc Northfield, MN 55057
plw@panda.UUCP (Pete Williamson) (02/12/86)
> >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
bs@faron.UUCP (Robert D. Silverman) (02/14/86)
> > > >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
jim@randvax.UUCP (Jim Gillogly) (02/17/86)
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
bs@faron.UUCP (Robert D. Silverman) (02/19/86)
> 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
jlg@lanl.ARPA (Jim Giles) (02/19/86)
In article <476@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >... 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. >.... >Bob Silverman A minor correction: the number was factored on an X/MP-24 here at Los Alamos. The Sandia team wrote the code. (I had a very slight interest in this - I rewrote the Fortran intrinsic MOD function for this code to gain a 5% speed-up.) J Giles Los Alamos (10^71 - 1)/9 = 241,573,142,393,627,673,576,957,439,049 * 45,994,811,347,886,846,310,221,728,895,223,034,301,839
falk@sun.uucp (Ed Falk) (02/20/86)
> > > > 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