RSA Laboratories

RSA-140 is factored!

On February 2, 1999, a group of researchers completed the factorization of the 140 digit RSA Challenge Number.  The work was accomplished with the General Number Field Sieve.  Here are the details of the work:

Sieving was performed on about 125 SGI and Sun workstations running at 175 MHz on average, and on about 60 PCs running at 300 MHz on average. The elapsed time was one month and the total amount of CPU-time spent on sieving was 8.9 CPU years. The sieving software used two different sieve techniques: line sieving and lattice sieving.  The line sieving software required 26 Mbytes/machine and the lattice sieving software required about 50 Mbytes/machine to run.  The sieving was accomplished as follows:

36.8 %

Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, Walter M. Lioen (C,L at CWI, Amsterdam, The Netherlands)

28.8 %

Paul C Leyland (L at Microsoft Research Ltd, Cambridge, UK)

26.6 %

Bruce Dodson (C,L at Lehigh University, Bethlehem, PA, USA)

5.4 %

Paul Zimmermann (L at Inria Lorraine and Loria, Nancy, France)

2.5 %

Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA, and at the University of Sydney, Australia)

The resulting matrix had 4671181 rows and 4704451 columns, and weight 151141999 (32.36 nonzeros per row). Peter Montgomery's Cray implementation of the blocked Lanczos algorithm  took almost 100 CPU hours and 810 Mbytes of central memory on the Cray C916 at the SARA Amsterdam Academic Computer Center to solve.

The amount of CPU time closely matches what would be expected based upon the prior effort to factor RSA-130.  A 155 digit number (512 bits)  should be about 7.2 times harder in terms of time and 2.7 times harder in terms of memory requirments, for both the sieving machines and the matrix. A 1024-bit number will be about 40 Million times harder in terms of time, and  6300 times harder in terms of space.  These last estimates are just gross approximations of course and are somewhat conservative.

A fairly extensive effort was expended in order to select the polynomials. They were selected with the help of a new polynomial search method developed by Peter Montgomery and Brian Murphy (The Australian National University, Canberra).  The selection took 2000 CPU hours on four 250 MHz SGI Origin 2000 processors at CWI. Calendar time for the polynomial selection was four weeks. This time was well worth the effort as good polynomial selection can greatly reduce the sieving time.

Top of Page