Integer factorization records

Last updated

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

Contents

Numbers of a general form

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 Cray C916 supercomputer at the SARA Amsterdam Academic Computer Center.

In January 2002, it was 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.

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 SGI Origin 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 21826 + 1.

A 176-digit cofactor of 11281 + 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 (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. [3] They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron.

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]

Numbers of a special form

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

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

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

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

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

21061 − 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 additional 35 CPU-years. [13]

All unfactored parts of the numbers 2n − 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.

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 via ggnfs [15] and of robust open-source software such as msieve [16] 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. [17] These bounds increase to about 950 bits (286 digits) [18] and 600 bits (181 digits) [19] 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, a 512-bit (155-digit) RSA key was factored used to sign the TI-83 graphing calculator using software found on the internet; this eventually led to the Texas Instruments signing key controversy.

In September 2013, the 696-bit (210-digit) RSA-210 was factored [20] using institutional resources; between March 2013 and October 2014, another 210-digit number (the 117th term in the home prime sequence starting with 49), [21] using $7600 worth of processing time on Amazon EC2 machines [22] for the sieving, and four months on a dual Xeon E5-2687W v1 for the linear algebra.

Records for efforts by quantum computers

The largest number reliably factored[ clarification needed ] by Shor's algorithm is 21 which was factored in 2012. [23] 15 had previously been factored by several labs.

In April 2012, the factorization of 143 = 13 × 11 by a room-temperature (300 K) NMR adiabatic quantum computer was reported by a group. [24] In November 2014 it was discovered that the 2012 experiment had in fact also factored much larger numbers without knowing it. [ clarification needed ] [25] [26] In April 2016 the 18-bit number 200,099 was factored using quantum annealing on a D-Wave 2X quantum processor. [27] Shortly after, 291 311 was factored using NMR at higher than room temperature. [28] In late 2019, Zapata computing claimed to have factored 1,099,551,473,989, [29] and in 2021 released a paper describing this computation. [30] 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. [31]

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. [32] [33] 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. [30] 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.

See also

Related Research Articles

In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a composite number, or it is not, in which case it is a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

<span class="mw-page-title-main">Quantum computing</span> Computer hardware technology that uses quantum mechanics

A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. Theoretically a large-scale quantum computer could break some widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.

<span class="mw-page-title-main">Qubit</span> Basic unit of quantum information

In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two spin states can also be measured as horizontal and vertical linear polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of multiple states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) (read "the index of a to the base r modulo m") for r x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in quantum computers make this prediction uncertain due to Shor's algorithm.

In mathematics, the RSA numbers are a set of large semiprimes that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.

"The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American. It was solved in 1993–94 by a large, joint computer project co-ordinated by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland. More than 600 volunteers contributed CPU time from about 1,600 machines over six months. The coordination was done via the Internet and was one of the first such projects.

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than the square root of n.

Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic-group factorisation algorithm.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.

<span class="mw-page-title-main">D-Wave Systems</span> Canadian quantum computing company

D-Wave Quantum Systems Inc. is a quantum computing company with locations in Palo Alto, California and Burnaby, British Columbia. D-Wave claims to be the world's first company to sell computers that exploit quantum effects in their operation. D-Wave's early customers include Lockheed Martin, the University of Southern California, Google/NASA, and Los Alamos National Laboratory.

<span class="mw-page-title-main">Texas Instruments signing key controversy</span> Refers to Texas Instruments response to a project to factorize cryptographic keys.

The Texas Instruments signing key controversy resulted from Texas Instruments' (TI) response to a project to factorize the 512-bit RSA cryptographic keys needed to write custom firmware to TI devices.

Discrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation given elements g and h of a finite cyclic group G. The difficulty of this problem is the basis for the security of several cryptographic systems, including Diffie–Hellman key agreement, ElGamal encryption, the ElGamal signature scheme, the Digital Signature Algorithm, and the elliptic curve cryptography analogues of these. Common choices for G used in these algorithms include the multiplicative group of integers modulo p, the multiplicative group of a finite field, and the group of points on an elliptic curve over a finite field.

<span class="mw-page-title-main">Quantum machine learning</span> Interdisciplinary research area at the intersection of quantum physics and machine learning

Quantum machine learning is the integration of quantum algorithms within machine learning programs.

The DiVincenzo criteria are conditions necessary for constructing a quantum computer, conditions proposed in 1996 by the theoretical physicist David P. DiVincenzo, as being those necessary to construct such a computer—a computer first proposed by mathematician Yuri Manin, in 1980, and physicist Richard Feynman, in 1982—as a means to efficiently simulate quantum systems, such as in solving the quantum many-body problem.

References

  1. ↑ "Factorization of 176-digit number" . Retrieved 2007-05-23.
  2. ↑ "RSA200" . Retrieved 2007-05-23.
  3. ↑ "Factorization of a 768-bit RSA modulus" (PDF). Retrieved 2013-04-11.
  4. ↑ "[Cado-NFS-discuss] 795-bit factoring and discrete logarithms". Archived from the original on 2019-12-02. Retrieved 2019-12-03.
  5. ↑ F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," June 10, 2020.
  6. ↑ "LISTSERV - NMBRTHRY Archives - LISTSERV.NODAK.EDU".
  7. ↑ P. L. Montgomery. "Record Number Field Sieve Factorisations" . Retrieved 2007-11-23.
  8. ↑ The Cabal. "233-digit SNFS factorization". Archived from the original on 2007-11-28. Retrieved 2007-11-23.
  9. ↑ J. Franke. "M809". Archived from the original on 2007-08-23. Retrieved 2007-11-23.
  10. ↑ "SNFS274" . Retrieved 2007-05-23.
  11. ↑ "Factorization of the 1039th Mersenne number" . Retrieved 2007-05-23.
  12. ↑ "A kilobit special number field sieve factorization" . Retrieved 2007-12-19.
  13. ↑ Greg Childers (2012). "Factorization of a 1061-bit number by the Special Number Field Sieve". Cryptology ePrint Archive.
  14. ↑ "Mersenne Factorization Factory" . Retrieved 2015-01-18.
  15. ↑ "GGNFS suite – Browse Files at SourceForge.net". sourceforge.net.
  16. ↑ "Archived copy". Archived from the original on 2007-12-13. Retrieved 2007-11-23.{{cite web}}: CS1 maint: archived copy as title (link)
  17. ↑ "mersenneforum.org – View Single Post – 2LM Table". www.mersenneforum.org.
  18. ↑ "mersenneforum.org – View Single Post – A computation worthy of the name". www.mersenneforum.org.
  19. ↑ "mersenneforum.org – View Single Post – 5^421-1 sieving (reservations closed)". www.mersenneforum.org.
  20. ↑ "RSA-210 factored – mersenneforum.org". mersenneforum.org.
  21. ↑ "mersenneforum.org – View Single Post – HP49(119)..." www.mersenneforum.org.
  22. ↑ "Archived copy". Archived from the original on 2021-04-16. Retrieved 2020-03-04.{{cite web}}: CS1 maint: archived copy as title (link)
  23. ↑ "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. 12 October 2012. arXiv: 1111.4147 . Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID   46546101.
  24. ↑ "143 is largest number yet to be factored by a quantum algorithm".
  25. ↑ "New largest number factored on a quantum device is 56,153".
  26. ↑ "The Mathematical Trick That Helped Smash The Record For The Largest Number Ever Factorised By A..." 2 December 2014.
  27. ↑ "Prime factorization using quantum annealing and computational algebraic geometry". Scientific Reports. 7: 43048. 21 February 2017. arXiv: 1604.05796 . Bibcode:2017NatSR...743048D. doi:10.1038/srep43048. PMC   5318873 . PMID   28220854.
  28. ↑ A bot will complete this citation soon. Click here to jump the queue arXiv : 1706.08061 .
  29. ↑ Crane, Leah. "Quantum computer sets new record for finding prime number factors". New Scientist. Retrieved 2020-10-02.
  30. 1 2 "Analyzing the performance of variational quantum factoring on a superconducting quantum processor". npj Quantum Information. 7: 156. 28 October 2021. arXiv: 2012.07825 . Bibcode:2021npjQI...7..156K. doi:10.1038/s41534-021-00478-z. S2CID   229156747.
  31. ↑ "Effective prime factorization via quantum annealing by modular locally-structured embedding". Scientific Reports. 14 (1): 3518. 12 February 2024. arXiv: 2310.17574 . Bibcode:2024NatSR..14.3518D. doi:10.1038/s41598-024-53708-7. PMC   10861481 . PMID   38347002.
  32. ↑ Gidney, Craig. "Factoring the largest number ever with a quantum computer". Blog. Retrieved 2022-07-18.
  33. ↑ Smolin, John A. (2013). "Oversimplifying quantum factoring". Nature. 499 (7457): 163–165. arXiv: 1301.7007 . Bibcode:2013Natur.499..163S. doi:10.1038/nature12290. PMID   23846653. S2CID   118613892.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.