Editing Integer factorization (section)

== Current state of the art ==
{{See also|Integer factorization records}}

Among the {{math|''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.

In 2019, a 240-digit (795-bit) number ([[RSA-240]]) was factored by a team of researchers including [[Paul Zimmermann (mathematician)|Paul Zimmermann]], 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> These researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.<ref name=rsa768>{{cite conference
 | last1 = Kleinjung | first1 = Thorsten
 | last2 = Aoki | first2 = Kazumaro
 | last3 = Franke | first3 = Jens
 | last4 = Lenstra | first4 = Arjen K.
 | last5 = Thomé | first5 = Emmanuel
 | last6 = Bos | first6 = Joppe W.
 | last7 = Gaudry | first7 = Pierrick
 | last8 = Kruppa | first8 = Alexander
 | last9 = Montgomery | first9 = Peter L.
 | last10 = Osvik | first10 = Dag Arne
 | last11 = te Riele | first11 = Herman J. J.
 | last12 = Timofeev | first12 = Andrey
 | last13 = Zimmermann | first13 = Paul
 | editor-last = Rabin | editor-first = Tal
 | contribution = Factorization of a 768-Bit RSA Modulus
 | contribution-url = https://eprint.iacr.org/2010/006.pdf
 | doi = 10.1007/978-3-642-14623-7_18
 | pages = 333–350
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings
 | volume = 6223
 | year = 2010| isbn = 978-3-642-14622-0
 }}</ref>

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&nbsp;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.

=== Time complexity ===

No [[algorithm]] has been published that can factor all integers in [[polynomial time]], that is, that can factor a {{math|''b''}}-bit number {{math|''n''}} in time {{math|[[Big O notation|O]](''b''<sup>''k''</sup>)}} for some constant {{math|''k''}}. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist.<ref>{{citation |last=Krantz |first=Steven G. |author-link=Steven G. Krantz |doi=10.1007/978-0-387-48744-1 |isbn=978-0-387-48908-7 |location=New York |mr=2789493 |page=203 |publisher=Springer |title=The Proof is in the Pudding: The Changing Nature of Mathematical Proof |url=https://books.google.com/books?id=mMZBtxVZiQoC&pg=PA203 |year=2011}}</ref><ref>{{citation |last1=Arora |first1=Sanjeev |author1-link=Sanjeev Arora |last2=Barak |first2=Boaz |doi=10.1017/CBO9780511804090 |isbn=978-0-521-42426-4 |location=Cambridge |mr=2500087 |page=230 |publisher=Cambridge University Press |title=Computational complexity |url=https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA230 |year=2009|s2cid=215746906 }}</ref>

There are published algorithms that are faster than {{math|O((1 + ''ε'')<sup>''b''</sup>)}} for all positive {{math|''ε''}}, that is, [[Time complexity#Sub-exponential time|sub-exponential]].  {{As of|2022}}, the algorithm with best theoretical asymptotic running time is the [[general number field sieve]] (GNFS), first published in 1993,<ref>{{cite book |last1=Buhler |first1=J. P. |last2=Lenstra |first2=H. W. Jr. |last3=Pomerance |first3=Carl |chapter=Factoring integers with the number field sieve |title=The development of the number field sieve |date=1993 |publisher=Springer |isbn=978-3-540-57013-4 |pages=50–94 |doi=10.1007/BFb0091539 |hdl=1887/2149 |series=Lecture Notes in Mathematics |volume=1554 |url=https://doi.org/10.1007/BFb0091539 |access-date=12 March 2021 |language=English}}</ref> running on a {{math|''b''}}-bit number {{math|''n''}} in time:
: <math>\exp\left( \left(\left(\tfrac83\right)^\frac23 + o(1)\right)\left(\log n\right)^\frac13\left(\log \log n\right)^\frac23\right).</math>

For current computers, GNFS is the best published algorithm for large {{math|''n''}} (more than about 400 bits). For a [[Quantum computing|quantum computer]], however, [[Peter Shor]] discovered an algorithm in 1994 that solves it in polynomial time. [[Shor's algorithm]] takes only {{math|O(''b''<sup>3</sup>)}} time and {{math|O(''b'')}} space on {{math|''b''}}-bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using [[Nuclear magnetic resonance|NMR]] techniques on molecules that provide seven qubits.<ref>
{{cite journal
 | doi = 10.1038/414883a
 | title = Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
 | journal = [[Nature (journal)|Nature]]
 | volume = 414
 | pages = 883–887
 | year = 2001
 | last = Vandersypen | first=Lieven M. K. | issue = 6866
 | display-authors=etal| arxiv = quant-ph/0112176
 | pmid = 11780055
 | bibcode = 2001Natur.414..883V
 | s2cid = 4400832
}}</ref>

In order to talk about [[complexity class|complexity classes]] such as P, NP, and co-NP, the problem has to be stated as a [[decision problem]].

{{Math theorem |For every natural numbers <math>n</math> and <math>k</math>, does {{math|''n''}} have a factor smaller than {{math|''k''}} besides 1? |name=Decision problem |note=Integer factorization }}

It is known to be in both [[NP (complexity)|NP]] and [[co-NP]], meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization {{math|1=''n'' = ''d''({{sfrac|''n''|''d''}})}} with {{math|''d'' ≤ ''k''}}. An answer of "no" can be certified by exhibiting the factorization of {{math|''n''}} into distinct primes, all larger than {{math|''k''}}; one can verify their primality using the [[AKS primality test]], and then multiply them to obtain {{math|''n''}}. The [[fundamental theorem of arithmetic]] guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both [[UP (complexity)|UP]] and co-UP.<ref>
{{cite web
 | author = Lance Fortnow
 | title = Computational Complexity Blog: Complexity Class of the Week: Factoring
 | date = 2002-09-13
 | url = http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html
}}</ref> It is known to be in [[BQP]] because of Shor's algorithm.

The problem is suspected to be outside all three of the complexity classes P, NP-complete,<ref>{{citation |last1=Goldreich |first1=Oded |author1-link=Oded Goldreich |last2=Wigderson |first2=Avi |author2-link=Avi Wigderson |editor1-last=Gowers |editor1-first=Timothy |editor1-link=Timothy Gowers |editor2-last=Barrow-Green |editor2-first=June |editor2-link=June Barrow-Green|editor3-last=Leader |editor3-first=Imre |editor3-link=Imre Leader |contribution=IV.20 Computational Complexity |isbn=978-0-691-11880-2 |location=Princeton, New Jersey |mr=2467561 |pages=575–604 |publisher=Princeton University Press |title=The Princeton Companion to Mathematics |year=2008}}. See in particular [https://books.google.com/books?id=ZOfUsvemJDMC&pg=PA583 p.&nbsp;583].</ref> and [[co-NP-complete]].
It is therefore a candidate for the [[NP-intermediate]] complexity class.

In contrast, the decision problem "Is {{math|''n''}} a composite number?" (or equivalently: "Is {{math|''n''}} a prime number?") appears to be much easier than the problem of specifying factors of {{math|''n''}}. The composite/prime problem can be solved in polynomial time (in the number {{math|''b''}} of digits of {{math|''n''}}) with the [[AKS primality test]]. In addition, there are several [[randomized algorithm|probabilistic algorithm]]s that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of [[primality test]]ing is a crucial part of the [[RSA (algorithm)|RSA]] algorithm, as it is necessary to find large prime numbers to start with.