Content deleted Content added
m within the phrase "integer factorization algorithm" is not a helpful context to link to a more general concept of 'factorization' |
move paragraph about 2019 results to the "Current state of the art" section |
||
Line 6:
When the numbers are sufficiently large, no efficient [[quantum computer|non-quantum]] integer factorization [[algorithm]] is known. However, it has not been proven that such an algorithm does not exist. The presumed [[Computational hardness assumption|difficulty]] of this problem is important for the algorithms used in [[cryptography]] such as [[RSA (cryptosystem)|RSA public-key encryption]] and the [[Digital Signature Algorithm|RSA digital signature]].<ref>{{Citation |last=Lenstra |first=Arjen K. |title=Integer Factoring |date=2011 |url=http://link.springer.com/10.1007/978-1-4419-5906-5_455 |encyclopedia=Encyclopedia of Cryptography and Security |pages=611–618 |editor-last=van Tilborg |editor-first=Henk C. A. |place=Boston, MA |publisher=Springer US |language=en |doi=10.1007/978-1-4419-5906-5_455 |isbn=978-1-4419-5905-8 |access-date=2022-06-22 |editor2-last=Jajodia |editor2-first=Sushil}}</ref> Many areas of [[mathematics]] and [[computer science]] have been brought to bear on the problem, including [[elliptic curve]]s, [[algebraic number theory]], and [[quantum computer|quantum computing]].
In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number ([[RSA-240]]) utilizing approximately 900 core-years of computing power.<ref>{{cite web| url = https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html| url-status = dead| archive-url = https://web.archive.org/web/20191202190004/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html| archive-date = 2019-12-02| title = [Cado-nfs-discuss] 795-bit factoring and discrete logarithms}}</ref> The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.<ref name=rsa768>{{cite journal▼
| url = http://eprint.iacr.org/2010/006.pdf▼
| title = Factorization of a 768-bit RSA modulus▼
| author = Kleinjung| publisher = [[International Association for Cryptologic Research]]▼
| date = 2010-02-18▼
| access-date = 2010-08-09▼
|display-authors=etal}}</ref>▼
Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are [[semiprime]]s, the product of two prime numbers. When they are both large, for instance more than two thousand [[bit]]s long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by [[Fermat's factorization method]]), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically.
Line 27 ⟶ 19:
== Current state of the art ==
{{See also|Integer factorization records}}
▲In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number ([[RSA-240]]) utilizing approximately 900 core-years of computing power.<ref>{{cite web| url = https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html| url-status = dead| archive-url = https://web.archive.org/web/20191202190004/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html| archive-date = 2019-12-02| title = [Cado-nfs-discuss] 795-bit factoring and discrete logarithms}}</ref> The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.<ref name=rsa768>{{cite journal
▲| url = http://eprint.iacr.org/2010/006.pdf
▲| title = Factorization of a 768-bit RSA modulus
▲| author = Kleinjung| publisher = [[International Association for Cryptologic Research]]
▲| date = 2010-02-18
▲| access-date = 2010-08-09
▲|display-authors=etal}}</ref>
Among the ''b''-bit numbers, the most difficult to factor in practice using existing algorithms are those [[semiprimes]] whose factors are of similar size. For this reason, these are the integers used in cryptographic applications. The largest such semiprime yet factored was [[RSA numbers#RSA-250|RSA-250]], an 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using Intel [[Skylake (microarchitecture)#Xeon Gold (quad processor)|Xeon Gold]] 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the [[general number field sieve]] run on hundreds of machines.
| |||