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 that have no small factors).

The first enormous distributed factorisation was RSA-129, a 129-digit 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 through 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 155-digit 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 CrayC916 supercomputer at the SARA Amsterdam Academic Computer Center.

In January 2002, it was 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 the 160-digit RSA-160 using about a hundred CPUs at BSI, with the final stages of the calculation done using 25 processors of an SGIOrigin supercomputer.

The 576-bit (174-digit) RSA-576 was factored by members of the NFSNET collaboration in December 2003, using resources at BSI and the University of Bonn; soon afterwards it was announced a group factored a 164-digit cofactor of 2¹⁸²⁶ + 1.

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

The 663-bit (200-digit) RSA-200 challenge number was factored 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 factored the slightly smaller RSA-640 challenge number in November 2005.

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.^[3] They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMDOpteron.

In November 2019, the 795-bit (240-digit) RSA-240 was factored.^[4][5]

In February 2020, the factorization of the 829-bit (250-digit) RSA-250 was completed.^[6]

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

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.^[8]

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. The linear algebra step was done at SARA in Amsterdam.^[9]

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

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 at NTT, EPFL and the University of Bonn.^[11][12]

2¹⁰⁶¹ − 1, of 1061 bits (320 digits) was factored between early 2011 and 4 August 2012 by a group 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 and needed an additional 35 CPU-years.^[13]

All unfactored parts of the numbers 2ⁿ − 1 with n between 1000 and 1200 were factored by a multiple-number-sieve approach in which much of the sieving step could be done simultaneously for multiple numbers, starting in 2010.^[14] To be precise, n = 1081 (326 digits) was completed on 11 March 2013; n = 1111 (335 digits) on 13 June 2013; n = 1129 (340 digits) on 20 September 2013; n = 1153 (348 digits) on 28 October 2013; n=1159 (349 digits) on 9 February 2014; n = 1177 (355 digits) on 29 May 2014, n = 1193 (360 digits) on 22 August 2014, and n = 1199 (361 digits) on 11 December 2014; the first detailed announcement was made in late August 2014. The total effort for the project is of the order of 7500 CPU-years on 2.2 GHz Opterons, with roughly 5700 years spent sieving and 1800 years on linear algebra.

The record of the prime factor other than the ultimate prime factor has 155 decimal digits; it is a prime factor of 12³¹¹−1.^[15][16][17]

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 via ggnfs^[18] and of robust open-source software such as msieve^[19] for the finishing stages, special-form numbers of up to 750 bits (226 digits) and general-form numbers of up to about 520 bits (157 digits) can be factored in a few months on a few PCs by a single person without any special mathematical experience.^[20] These bounds increase to about 950 bits (286 digits)^[21] and 600 bits (181 digits)^[22] 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.

En 2009, se descifró una clave RSA de 512 bits (155 dígitos). Esta clave se había utilizado para firmar la calculadora gráfica TI-83 mediante un software encontrado en internet; esto finalmente dio lugar a la controversia sobre la clave de firma de Texas Instruments .

En septiembre de 2013, el RSA-210 de 696 bits (210 dígitos) fue factorizado ^{[ 23 ]} utilizando recursos institucionales; entre marzo de 2013 y octubre de 2014, otro número de 210 dígitos (el término 117 en la secuencia de primos de origen que comienza con 49), ^{[ 24 ]} utilizando $7600 de tiempo de procesamiento en máquinas Amazon EC2 ^{[ 25 ]} para el cribado, y cuatro meses en un Xeon E5-2687W  v1 dual para el álgebra lineal.

El número más grande factorizado de manera confiable por el algoritmo de Shor , en lugar de algún otro método cuántico, es 21, que fue factorizado en 2012. ^{[ 26 ] [ 27 ]} El número 15 había sido factorizado previamente por varios laboratorios y los intentos posteriores de factorizar 35 fracasaron. ^{[ 27 ]}

Se han utilizado otros métodos para factorizar números específicos en computadoras cuánticas. En abril de 2012, un grupo informó sobre la factorización de 143  =  13  × 11 mediante una computadora cuántica adiabática  de RMN a temperatura ambiente (300  K) . ^{[ 28 ]} En noviembre de 2014 se descubrió que el experimento de 2012 también había factorizado números mucho mayores sin saberlo. ^{[ 29 ] [ 30 ]} En abril de 2016, el número de 18 bits 200,099 se factorizó utilizando recocido cuántico en un procesador cuántico D-Wave 2X . ^{[ 31 ]} Poco después, el número 291,311 se factorizó utilizando RMN a una temperatura superior a la ambiente. ^{[ 32 ]} A finales de 2019, Zapata Computing afirmó haber factorizado 1.099.551.473.989, ^{[ 33 ]} y en 2021 publicó un artículo que describía este cálculo. ^{[ 34 ]} En 2024, se propuso un nuevo enfoque para integrar problemas de factorización de números primos en recocedores cuánticos, lo que llevó a (i) la integración de problemas de factorización de números primos de 21×12 en una arquitectura D-Wave Pegasus; (ii) la factorización de 8.219.999 mediante un recocedor cuántico sin explotar técnicas híbridas. ^{[ 35 ]}

As such, claims of factoring with quantum computers have however been criticized for depending heavily on classical computation to reduce the number of qubits required.^[36][37] For example, the factorization of 1,099,551,473,989 relied on classical pre-processing to reduce the problem to a three-qubit quantum circuit.^[34] Furthermore, the three numbers factored in this paper (200,099, 291,311, and 1,099,551,473,989) can easily be factored using Fermat's factorization method, requiring only 3, 1, and 1 iterations of the loop respectively. In 2025, existing factorisation records using a quantum computer were replicated using a VIC-20, highlighting the ease of factoring numbers with particular structures.^[27]

• Largest known prime number