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).

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). All unfactored parts of the numbers 2 n  − 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. 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. 2 1277  − 1, of 1277 bits (385 digits), was factored in September 2026, this number is the current record of special number field sieve. Other methods have been used to factorise specific numbers on quantum computers. In April 2012, the factorization of 143 = 13 × 11 by a room-temperature (300 K) NMR adiabatic quantum computer was reported by a group. In November 2014 it was discovered that the factorisation of other numbers could lead to the same equations that were solved in the 2012 paper, thus the 2012 experiment could be considered to have also factored much larger numbers without knowing it. In April 2016 the 18-bit number 200,099 was factored using quantum annealing on a D-Wave 2X quantum processor. Shortly after, the number 291,311 was factored using NMR at higher than room temperature. In late 2019, Zapata computing claimed to have factored 1,099,551,473,989, and in 2021 released a paper describing this computation. In 2024, a new approach to embed prime factoring problems into quantum annealers has been proposed, leading to (i) the embedding of 21×12 prime factoring problems into a D-Wave Pegasus architecture; (ii) the factoring of 8,219,999 by using a quantum annealer without exploiting hybrid techniques. 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. 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378645533 under CC BY-SA 4.0; modifications have been made.