Integer factorization records
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it is currently very difficult to factorize large semiprimes (and, indeed, most numbers which have no small factors).
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 2953+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.
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 21826+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. They later (November 2005) factored the slightly smaller RSA-640 challenge number.
On December 12, 2009, a team including researchers from the CWI, the EPFL, INRIA and NTT in addition to the authors of the previous record factored RSA-768, a 232-digit semiprime. They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron.
Numbers of a special form
2773 + 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.
2809 − 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.
21039 − 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.
21061 − 1, of 1061 bits (320 digits) was factored between early 2011 and 4 August 2012 by a group headed by Greg Childers at CSU Fullerton, using the nfs@home BOINC project for about 300 CPU-years of sieving; the linear algebra was run at the Trestles cluster at SDSC and the Lonestar cluster at TACC.
All unfactored parts of the numbers 2n − 1 with n between 1000 and 1200 are in the process of being factored by a multiple-number-sieve approach in which much of the sieving step could be done simultaneously for multiple numbers, by a group including T. Kleinjung, J. Bos and A. K. Lenstra, starting in 2010.  To be precise, 1081 was completed on 11 March 2013; 1111 on 13 June 2013; 1129 on 20 September 2013; 1153 on 28 October 2013; 1159 on 9 February 2014; 1177 on May 29 2014 and 1193 on 22 August 2014, though no detailed announcement was made until late August. The total effort for the project is of the order of 5000 CPU-years on 2.2GHz Opterons. As of 23rd of October 2014 their largest published result was the unfactored part of 21193 − 1, at 1177 bits (355 digits).
Comparison to efforts 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 efficient sieving code (developed by Thorsten Kleinjung of the Bonn group) via ggnfs and of 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. These bounds increase to about 950 and 600  if it were possible to secure the collaboration of a few dozen PCs for sieving; currently the amount of memory and the CPU power of a single machine for the finishing stage are equal barriers to progress.
In 2009, Benjamin Moody factored a 512-bit RSA key used to sign the TI-83 graphing calculator using software found on the internet; this eventually led to the Texas Instruments signing key controversy.
- K. Aoki, Y. Kida, T. Shimoyama, H. Ueda. "Factorization of 176-digit number". Retrieved 2007-05-23.
- F. Bahr, M. Boehm, J. Franke, T. Kleinjung. "RSA200". Retrieved 2007-05-23.
- T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. te Riele, A. Timofeev, P. Zimmermann. "Factorization of a 768-bit RSA modulus". Retrieved 2013-04-11.
- P. L. Montgomery. "Record Number Field Sieve Factorisations". Retrieved 2007-11-23.
- 'The Cabal'. "233-digit SNFS factorization". Retrieved 2007-11-23.
- J. Franke. "M809". Retrieved 2007-11-23.
- K. Aoki, Y. Kida, T. Shimoyama, H. Ueda. "SNFS274". Retrieved 2007-05-23.
- K. Aoki, J. Franke, T. Kleinjung, A. K. Lenstra, D. A. Osvik. "Factorization of the 1039th Mersenne number". Retrieved 2007-05-23.
- Kazumaro Aoki and Jens Franke and Thorsten Kleinjung and Arjen Lenstra and Dag Arne Osvik. "A kilobit special number field sieve factorization". Retrieved 2007-12-19.
- Greg Childers. "Factorization of a 1061-bit number by the Special Number Field Sieve".
- Thorsten Kleinjung, Joppe W Bos, Arjen K Lenstra. "Mersenne Factorization Factory". Retrieved 2014-10-23.
- 518-bit example
- 941-bit SNFS done in late 2009
- 598-bit factorisation done over five months in late 2008