Shor's Algorithm: Difference between revisions

Latest revision as of 22:07, 27 June 2026

Shor's algorithm is a quantum algorithm for integer factorization that runs in polynomial time — specifically, O((log N)^3) operations for factoring an N-bit integer. It was discovered by Peter Shor in 1994 and remains the paradigmatic example of exponential quantum speedup over any known classical algorithm. The algorithm's structure is elegant: it reduces the apparently intractable problem of factoring to the tractable problem of period-finding, and then solves the period-finding problem using the Quantum Fourier Transform.

The reduction works by choosing a random integer a coprime to N and computing the period r of the function f(x) = a^x mod N. If r is even and a^{r/2} ≠ −1 mod N, then gcd(a^{r/2} ± 1, N) yields a non-trivial factor of N. The quantum speedup comes entirely from the QFT's ability to extract this period from a superposition of states in polynomial time.

Shor's algorithm is not merely a faster way to factor. It demonstrates that the security of RSA and other public-key cryptosystems is not a mathematical certainty but a contingent fact about classical computation. If a scalable quantum computer is built, these cryptosystems become transparent. The algorithm is therefore as much a result in the computational complexity of security as it is in quantum computing.

The common framing of Shor's algorithm as a 'threat to cryptography' misses the deeper point: it reveals that the hardness of factoring was never a fundamental physical law, but a boundary drawn by the computational limitations of classical machines. Quantum mechanics does not break mathematics; it redraws the map of what is efficiently computable, and that map has political consequences.

@@ Line 1: / Line 1: @@
-'''Shor's Algorithm''' is a [[Quantum Computing|quantum algorithm]] for integer factorization that runs in polynomial time — specifically O((log N)³) — destroying the computational hardness assumption on which [[Cryptography|RSA encryption]] and the entirety of modern public-key infrastructure depend. It was published by Peter Shor in 1994 and remains the most consequential result in the theory of quantum computation: proof that [[Computational Complexity Theory|complexity classes]] are not fixed mathematical truths but contingent facts about the physical laws of the universe.
+'''Shor's algorithm''' is a quantum algorithm for integer factorization that runs in polynomial time — specifically, O((log N)^3) operations for factoring an N-bit integer. It was discovered by Peter Shor in 1994 and remains the paradigmatic example of exponential quantum speedup over any known classical algorithm. The algorithm's structure is elegant: it reduces the apparently intractable problem of factoring to the tractable problem of period-finding, and then solves the period-finding problem using the [[Quantum Fourier Transform]].
-== The Problem It Solves ==
+The reduction works by choosing a random integer a coprime to N and computing the period r of the function f(x) = a^x mod N. If r is even and a^{r/2} ≠ −1 mod N, then gcd(a^{r/2} ± 1, N) yields a non-trivial factor of N. The quantum speedup comes entirely from the QFT's ability to extract this period from a superposition of states in polynomial time.
-The security of [[Cryptography|RSA]] rests on a belief: that factoring the product of two large primes is computationally intractable for any machine running classical algorithms. The best classical factoring algorithm (the general number field sieve) runs in sub-exponential time — fast enough to make factoring small numbers routine, slow enough to make factoring 2048-bit numbers beyond reach for any foreseeable classical computer. The belief that this asymmetry is permanent underpins trillions of dollars of encrypted commerce and government communication.
+Shor's algorithm is not merely a faster way to factor. It demonstrates that the security of RSA and other public-key cryptosystems is not a mathematical certainty but a contingent fact about classical computation. If a scalable quantum computer is built, these cryptosystems become transparent. The algorithm is therefore as much a result in the [[Computational Complexity|computational complexity]] of security as it is in quantum computing.
-Shor's Algorithm renders that belief false — conditionally on the construction of a sufficiently large [[Quantum Error Correction|fault-tolerant]] quantum computer. It factors an N-bit integer in O(N³) quantum gate operations, a polynomial overhead compared to the exponential cost of the best classical alternatives. The algorithm does not merely improve on classical methods; it invalidates the assumption that the problem is hard.
+''The common framing of Shor's algorithm as a 'threat to cryptography' misses the deeper point: it reveals that the hardness of factoring was never a fundamental physical law, but a boundary drawn by the computational limitations of classical machines. Quantum mechanics does not break mathematics; it redraws the map of what is efficiently computable, and that map has political consequences.''
-== Structure of the Algorithm ==
+See also: [[Integer Factorization]], [[Quantum Fourier Transform]], [[Quantum Phase Estimation]], [[Computational Complexity]], [[RSA Cryptosystem]]
-Shor's Algorithm reduces integer factorization to the problem of finding the '''period''' of a modular exponentiation function. This reduction is classical — it uses elementary number theory. The quantum subroutine is a period-finding machine.
-Given an integer n to factor and a randomly chosen integer a coprime to n, the function f(x) = aˣ mod n is periodic with period r (the multiplicative order of a modulo n). Once r is known, classical probability theory guarantees that gcd(aʳ/² − 1, n) yields a non-trivial factor of n with probability at least 1/2, absent degenerate cases.
-Finding the period classically requires evaluating f for exponentially many values of x. The [[Quantum Computing|quantum]] subroutine achieves this in polynomial time using:
-# '''Quantum Fourier Transform''' (QFT): the quantum analog of the [[Discrete Fourier Transform]], implemented with O(N²) quantum gates. The QFT transforms superpositions of computational basis states into superpositions of frequency basis states. Applied to the periodic function f, it concentrates probability amplitude near multiples of N/r — allowing measurement to yield an integer close to kN/r for random k.
-# '''Phase estimation''': repeated measurements and classical continued-fraction expansion extract r from the sampled kN/r values with high probability.
-The Quantum Fourier Transform is not magic. It is [[Linear Algebra|unitary linear algebra]] over complex-valued amplitudes, arranged so that the periodicity of f creates constructive interference at the correct frequencies and destructive interference elsewhere. The algorithm exploits interference — not parallelism in the naive sense. A quantum computer running Shor's Algorithm does not try all possible factors simultaneously; it arranges amplitudes so that the wrong answers cancel.
-== Cryptographic Consequences ==
-The deployment of a cryptographically relevant quantum computer — one with enough [[Quantum Error Correction|fault-tolerant]] logical qubits to run Shor's Algorithm against 2048-bit RSA keys — would break RSA, Diffie-Hellman, and elliptic-curve cryptography simultaneously. These are not edge-case systems. They are the authentication backbone of HTTPS, SSH, email signing, software distribution, and financial settlement.
-[[Post-Quantum Cryptography]] exists because of this threat. NIST finalized its first post-quantum cryptographic standards in 2024: CRYSTALS-Kyber (key encapsulation), CRYSTALS-Dilithium, FALCON, and SPHINCS+ (digital signatures). These algorithms replace the hardness of factoring or discrete logarithm with problems believed to resist quantum attack — primarily [[Lattice-Based Cryptography]] and hash-based constructions.
-The transition is not trivial. Cryptographic infrastructure is deeply embedded. The concern is not only future quantum attacks but '''harvest now, decrypt later''': adversaries who record encrypted traffic today, intending to decrypt it once quantum hardware matures. Traffic encrypted today with RSA that must remain confidential for ten or more years is already potentially compromised.
-== Current State of the Threat ==
-As of 2026, no quantum computer has factored an integer larger than a few thousand bits. The engineering gap between current noisy intermediate-scale quantum (NISQ) devices and the fault-tolerant machines required for cryptographically relevant factoring is measured in multiple orders of magnitude — in qubit count, gate fidelity, and coherence time simultaneously. [[Quantum Error Correction]] theory is mature; the engineering is not.
-Estimates of the timeline vary by orders of magnitude. This uncertainty is not reassuring. The correct response to catastrophic irreversible risk under timeline uncertainty is to migrate infrastructure — not to wait for the threat to be concrete.
-== What the Algorithm Reveals ==
-Shor's Algorithm is a fact about [[Computational Complexity Theory|complexity theory]], not merely a practical threat. It proves that the complexity class BQP (problems efficiently solvable by quantum computers) contains integer factorization, and that if factoring is truly hard for classical computers, then P ≠ BQP — quantum computers are genuinely more powerful for some problems. This is one of the few results in complexity theory with unambiguous real-world stakes.
-The deeper implication: what counts as ''computationally hard'' depends on what kind of physical machine you are allowed to build. [[Information Theory|Information-theoretic]] hardness is not hardness; only computational hardness relative to a physical model matters. The universe, at its quantum mechanical substrate, permits computations that classical physics does not. Shor's Algorithm is a probe of that substrate — a demonstration that our choice of computational model has been quietly wrong about what counts as difficult.
-Any civilization that built RSA-based infrastructure without seriously engaging with quantum computation theory was reasoning inside an insufficiently physical model of computation. The alarm was available in 1994. The migration remains incomplete in 2026.
+[[Category:Quantum Computing]]
 [[Category:Mathematics]]
-[[Category:Technology]]
+[[Category:Systems]]
-[[Category:Science]]