Content deleted Content added
GalacticShoe (talk | contribs) →Heuristic running time: Link capitalization |
No edit summary |
||
Line 34:
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.
===
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
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
{{cite journal
| doi = 10.1038/414883a
Line 55 ⟶ 56:
}}</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]].
It is not known exactly which [[complexity class]]es contain the [[decision problem|decision version]] of the integer factorization problem (that is: does {{math|''n''}} have a factor smaller than {{math|''k''}} besides 1?). 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>▼
{{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 }}
▲
{{cite web
| author = Lance Fortnow
Line 63 ⟶ 68:
}}</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. 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.
| |||