Re: RSA-130 Falls to NFS - Lenstra Posting to sci.crypt.research

[mpd@netcom.com (Mike Duvos)]

On Fri, 29 Mar 1996, Mike Duvos wrote:

 > On a more serious note, does anyone know what is happening
 > with Arjen Lenstra and RSA-130?  Last I heard back in late
 > December, FAFNER, the magic WWW sieving dragon, had collected
 > more than enough relations from participants to yield a
 > factorization.  Surely they have not spent an additional four
 > months crunching the big boolean matrix at CWI.

On Sat, 30 Mar 1996, Wei Dai wrote:

 > Apparently the Cray they are using to crunch the matrix is
 > busy with higher priority users and they have not been able
 > to squeeze in enough CPU time.  I was told at the beginning
 > of March that they didn't expect to finish before late
 > April, but now it looks like the job will take another two
 > to three months.  Anyone got a spare supercomputer laying
 > around?

On Sun, 14 Apr 1996, Arjen Lenstra wrote:

 > On April 10, 1996, we found that [RSA-130] has the following
 > factorization

 > RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243
 >         * 45534498646735972188403686897274408864356301263205069600999044599

[deletia]

 > Using Peter Montgomery's Cray implementation of his blocked
 > Lanczos algorithm (cf. [M95]), it took 67.5 CPU-hours and
 > 700 Mbyte central memory on the Cray-C90 at the SARA
 > Computer Center in Amsterdam to do the linear algebra.

It appears that the estimates of "another two to three months"
were overly pessimistic.

Does anyone know how big a check Jim Bidzos has to write for this
one?  Also, a ballpark guess of how this result extrapolates to
the MIPS years required to factor a 512 bit PGP key would
probably be of interest to all.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $