RSA-155 is factored!
On August 22, 1999, a group of researchers completed the factorization of the 155 digit (512 bit) RSA Challenge Number. The work was accomplished with the General Number Field Sieve. Here are the details of the work:
The sieving software used two different sieve techniques: line sieving and lattice sieving. The sieving was accomplished as follows:
Sieving: 35.7 CPU-years in total on...
|160||175-400 MHz SGI and Sun workstations|
|8||250 MHz SGI Origin 2000 processors|
|120||300-450 MHz Pentium II PCs|
|4||500 MHz Digital/Compaq boxes|
This CPU-effort is estimated to be equivalent to approximately 8000 MIPS years; calendar time for the sieving was 3.7 months.
124 722 179 relations were collected by eleven different sites, distributed as follows:
(L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI)
- 20.1 % (3057 CPU days) Alec Muffett (L)
- 17.5 % (2092) Paul Leyland (L,C)
- 14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L)
- 13.6 % (2222) Bruce Dodson (L,C)
- 13.0 % (1801) Francois Morain and Gerard Guillerm (L,C)
- 6.4 % (576) Joel Marchand (L,C)
- 5.0 % (737) Arjen K. Lenstra (L)
- 4.5 % (252) Paul Zimmermann (C)
- 4.0 % (366) Jeff Gilchrist (L)
- 0.65 % (62) Karen Aardal (L)
- 0.56 % (47) Chris and Craig Putnam (L)
The resulting matrix had 6699191 rows and 6711336 columns, and weight 417132631 (62.27 nonzeros per row).
Peter Montgomery's Cray implementation of the blocked Lanczos algorithm took 224 CPU hours and about 3.2 Gbytes of central memory on the Cray C916 at the SARA Amsterdam Academic Computer Center to solve. This matrix is about 50% larger, twice as dense and took 2.2 times as long to solve as that for RSA-140.
A fairly extensive effort was expended in order to select the polynomials for RSA-155. They were selected with the help of a new polynomial search method developed by Peter Montgomery and Brian Murphy (The Australian National University, Canberra). Calendar time for the polynomial selection was nine weeks but could have been reduced with the use of additional computers. This time was well worth the effort as good polynomial selection can greatly reduce the sieving time. Because RSA-155 spent more effort on polynomial selection than was spent on RSA-140 the researchers were able to find a significantly better polynomial. Whereas the polynomials for RSA-140 were about 8 times better than randomly selected ones, the ones for RSA-155 were about 13.5 times better. RSA-155 took 35.7 CPU-Years as opposed to 8.9 CPU-Years for RSA-140. This is within the rough range of estimates based on the factorization of RSA-140, though the CPU time was somewhat less than predicted due perhaps to statistical variations, as well as to the improved polynomial selection. There are theoretical limits to the extent to which polynomial selection can be improved, however.
The total calendar time for factoring RSA-155 was 5.2 months (March 17 - August 22) excluding polynomial selection time. If one includes polynomial selection, the total elapsed time was 7.4 months, whereas RSA-140 took about 9 weeks of elapsed time. It must be noted that polynomial selection could be greatly reduced in elapsed time by using more machines. Neither effort devoted many machines to this task.