Content deleted Content added
Jasper Deng (talk | contribs) Undid revision 1182694945 by NealKoblitz (talk) the article is linked for a reason. No need to dumb it down too much. Tags: Undo Mobile edit Mobile web edit Advanced mobile edit |
m →Difficulty and complexity: express ³√64/9 as (8/3)^(2/3) to match (ln ln n)^(2/3) |
||
Line 33:
There are published algorithms that are faster than {{nowrap|O((1 + ''ε'')<sup>''b''</sup>)}} for all positive ''ε'', 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 |title=Factoring integers with the number field sieve |date=1993 |publisher=Springer |isbn=978-3-540-57013-4 |pages=50–94 |doi=10.1007/BFb0091539 |hdl=1887/2149 |edition=Lecture Notes in Mathematics, vol 1554 |url=https://doi.org/10.1007/BFb0091539 |access-date=12 March 2021 |language=English}}</ref> running on a ''b''-bit number ''n'' in time:
: <math>\exp\left( \
For current computers, GNFS is the best published algorithm for large ''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. This will have significant implications for cryptography if quantum computation becomes scalable. [[Shor's algorithm]] takes only O(''b''<sup>3</sup>) time and O(''b'') space on ''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>
| |||