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