Editing Integer factorization (section)

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