Integer factorization records

From Wikipedia, the free encyclopedia

Contents 1 Numbers of a general form 2 Numbers of a special form 3 How do these compare to what can be done by individuals? 4 References

[edit] Numbers of a general form

The first very large distributed factorisation was RSA129, a challenge number described in the Scientific American article of 1977 which first popularised the RSA cryptosystem. It was factorised between September 1993 and April 1994, using MPQS, with relations contributed by about 600 people from all over the Internet, and the final stages of the calculation performed on a MasPar supercomputer at Bell Labs.

Between January and August 1999, RSA-155, a challenge number prepared by the RSA company, was factorised using GNFS with relations again contributed by a large group, and the final stages of the calculation performed in just over nine days on the Cray C916 supercomputer at the SARA Amsterdam Academic Computer Center.

In January 2002, Franke et al announced the factorisation of a 158-digit cofactor of 2⁹⁵³+1, using a couple of months on about 25 PCs at the University of Bonn, with the final stages done using a cluster of six Pentium-III PCs.

In April 2003, the same team factored RSA-160 using about a hundred CPUs at BSI, with the final stages of the calculation done using 25 processors of an SGI Origin supercomputer.

The 174-digit RSA-576 was factored by Franke, Kleinjung and members of the NFSNET collaboration in December 2003, using resources at BSI and the University of Bonn; soon afterwards, Aoki, Kida, Shimoyama, Sonoda and Ueda announced that they had factored a 164-digit cofactor of 2¹⁸²⁶+1.

A 176-digit cofactor of 11²⁸¹+1 was factored by Aoki, Kida, Shimoyama and Ueda between February and May 2005 using machines at NTT and Rikkyo University in Japan.^[1]

The RSA-200 challenge number was factored by Franke, Kleinjung et al between December 2003 and May 2005, using a cluster of 80 Opteron processors at BSI in Germany; the announcement was made on 9 May 2005.^[2] They later (November 2005) factored the slightly smaller RSA-640 challenge number.

[edit] Numbers of a special form

12¹⁵¹−1, of 542 bits (163 digits), was factored between April and July 1993 by a team at CWI and Oregon State University. ^[3]

2⁷⁷³+1, of 774 bits (233 digits), was factored between April and November 2000 by 'The Cabal', with the matrix step done over 250 hours on the Cray also used for RSA-155.^[4]

2⁸⁰⁹-1, of 809 bits (244 digits), had its factorisation announced at the start of January 2003. Sieving was done at the CWI, at the Scientific Computing Institute and the Pure Mathematics Department at Bonn University, and using private resources of J. Franke, T. Kleinjung and the family of F. Bahr. The linear algebra step was done by P. Montgomery at SARA in Amsterdam. ^[5]

6³⁵³−1, of 911 bits (275 digits), was factored by Aoki, Kida, Shimoyama and Ueda between September 2005 and January 2006 using SNFS.^[6]

2¹⁰³⁹−1, of 1039 bits (313 digits) (though a factor of 23 bits was already known) was factored between September 2006 and May 2007 by a group including K. Aoki, J. Franke, T. Kleinjung, A. K. Lenstra and D. A. Osvik, using computers at NTT, EPFL and the University of Bonn.^{[7] [8]}

[edit] How do these compare to what can be done by individuals?

As of the end of 2007, thanks to the constant decline in memory prices, the ready availability of multi-core 64-bit computers, and the availability of the Bonn group's efficient sieving code via ggnfs and robust open-source software such as msieve for the finishing stages, special-form numbers of up to 750 bits and general-form numbers of up to about 520 bits can be factored in a few months on a few PCs by a single person without any special mathematical experience (see [1] for a 518-bit example). These bounds would increase to about 850 and 570 if it were possible to secure the collaboration of a few dozen PCs; the limit is the amount of memory in a single machine.

[edit] References