B. Dodson's Home Page

Slides for last semester's Math 23 course are on Lehigh's Course site page and some old course files are in [old205]. To contact me, send e-mail to bad0@Lehigh.EDU.

An alternative cryptosystem, relying upon the difficulty of solving the "discrete logarithm problem" rather than factoring, was the topic of my seminar during Spring 1996. I'm interested in a particular case using "elliptic curves" (currently used in some cell phones), as well as a future case using number fields. Elliptic curves are also applied to factoring, and some old results using Lehigh's blaze cluster were reported in the Algorithmic Number Theory Symposium (ANTS VII), Berlin 2006. Readers at sites with access may view the paper at Springer online. Compare my initial report on the number theory listserve [p66ecmrecord]. Earlier results obtained using the old fire cluster are described at [ecmnet2004fin]. Further information may be obtained by following the ECMNET link; and compare Paul Zimmermann's listserve report [p59ecm60].

For information on the Number Field Sieve "GNFS" algorithm, an early reference was available by browsing the links from the Lehigh webpage for the RSA130 factoring challenge, all subsequently expired. This algorithm was used in an extensive data collection effort ("sieving"), which produced a gigantic sparse matrix with 3,500,000 columns. The matrix equation was solved on a Cray C90, using 62 hours of CPUtime, breaking a 430-bit RSA key (130 decimal digits) into two 65-digit primes. While the RSA cryptosytem, used to provide security for web browsers and computer operating systems, currently relies upon 768-bit or 1024-bit keys; our computation [gave] the largest key broken in public, and [was] described at AsiaCrypt'96, a cryptography conference. Subsequently, I had a part in breaking RSA-140, as described in the paper at Asiacrypt'99. Finally, see the published paper Factorization of a 512-bit RSA Modulus . (These numbers were part of "Cryptographic Challenges," specifically "The RSA Factoring Challenge", from RSA Laboratories. The 512-bit key is RSA-155, with 155-decimal digits.) The current record [still!!] is RSA-768 (with 232-decimal digits, 2010), which used a parallel version of the matrix solving software.

A publically available version ran on Lehigh's Corona cluster, using MPI. For comparison with 1996, I completed a factorization by solving a sparse matrix problem with 30.7 million columns that used 50K core hours on 128-cores of corona. For sieving results in 2005 obtained using Lehigh's SGI Origin computer cf. [snfs2004]. There are reports of an effort to factor RSA-896, with 270-decimal digits; as well as attempts to estimate the difficulty of RSA-1024, with 309-decimal digits (cf. Factoring Estimates for a 1024-bit RSA Modulus ).

Recently Paul Zimmermann reports that he expects his team to be involved in the factorization of RSA-1024 "around 2020-2025". They expect to remove another factor of two from the estimated sieving time from 2010, using improved polynomial selection. That is, by finding a number field that in particular has even more small algebraic primes.

To go to Lehigh's home page, click here.