Peter Shor is an American mathematician and computer scientist, best known for creating Shor’s algorithm, a quantum algorithm that can factor large integers exponentially faster than the best known classical algorithms. This discovery, made in 1994, is what made quantum computing go from a weird theoretical curiosity to a field with teeth.
Why it’s a big deal:
・Most modern encryption—like RSA—depends on the fact that factoring huge numbers (hundreds or thousands of digits long) is extremely hard for classical computers.
・Shor showed that a quantum computer, if sufficiently large and stable, could factor those numbers efficiently, which means it could theoretically break RSA encryption.
In short: Shor proved that quantum mechanics could shatter classical cryptography.
He didn’t build the computer himself (no one had one at the time), but his math made the race to build quantum hardware suddenly matter.
Peter Shor himself is still an active researcher—he’s a professor at MIT—and has also contributed to quantum error correction, which helps stabilize quantum computations that would otherwise fall apart due to decoherence.
The fascinating bit is that Shor’s algorithm is simultaneously a triumph of pure mathematics and a warning shot to the entire field of cybersecurity. It’s one of those rare ideas that makes both mathematicians and engineers sweat for entirely different reasons.
If you like, we could unpack how Shor’s algorithm actually works—using Fourier transforms and periodicity detection—or explore how current “post-quantum cryptography” is trying to outpace it.
Here are key materials and a sketch of his main theorems.
Milestone paper
The landmark paper is:
Title: “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” by Peter W. Shor. (arXiv)
URL (arXiv): https://arxiv.org/abs/quant-ph/9508027 (arXiv)
Also available (PDF): https://users.cs.duke.edu/~reif/courses/randlectures/Quantum.papers/shor.factoring.pdf (users.cs.duke.edu)
This is the main paper that introduced what we now colloquially call “Shor’s algorithm”.
On-YouTube talk
Here’s a solid video:
The Story of Shor’s Algorithm, Straight From the Source
Title: “The Story of Shor’s Algorithm, Straight From the Source | Peter Shor” on YouTube. It features Shor himself narrating the origin and ideas behind his algorithm.
Selected theorems / results by Shor
Here are several of his major contributions (I’ll call them “theorems/results” loosely) with rough description. Note: some are more informal results than neatly labeled “theorem-X”.
・ Quantum factoring & discrete log polynomial-time result
-
In the milestone paper above, Shor shows that a quantum computer (ideal, error-free) can factor integers and compute discrete logarithms in polynomial time (in the input size). (arXiv)
-
The significance: classically factoring and discrete log are believed to require super-polynomial time; Shor’s result flips that in the quantum setting.
・ Quantum error correcting codes / “Shor code”
-
In his work he introduced quantum error-correcting codes (e.g., encoding 1 logical qubit into 9 physical qubits) to protect quantum information. (Fiveable)
-
One concrete statement: “Given any possible unitary, measurement, or quantum operation on a one-error quantum code, the code can correct it.” (Windows On Theory)
This is a more technical theorem of his on error correction.
・ Fault‐tolerant quantum computation / threshold‐type results
-
Shor contributed to showing that quantum computers can perform arbitrarily long computations provided the physical error rate is below some threshold (rough version). (math.ucsd.edu)
-
While the full “quantum threshold theorem” was proven by others as well, Shor’s work laid much of the groundwork. (Wikipedia)
・ Quantum channel capacity (“hashing bound” / coherent information)
-
Shor also worked in quantum information theory: e.g. on the quantum channel capacity concept (though the full theorem is attributed to others too). (Wikipedia)
Here’s a consolidated narrative of four of Peter W. Shor’s most important theoretical results, each paired with the original paper and the exact theorem-level statements where available. No tables, just the flow of ideas and sources.
1. Polynomial-time quantum factoring and discrete logarithms
In his seminal paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” (arXiv:quant-ph/9508027), Shor rigorously proved that a quantum computer can factor integers and compute discrete logarithms in time polynomial in the size of the input number.
The core theorem is stated as follows:
“A quantum computer can find the period of a periodic function and hence factor integers and compute discrete logarithms in polynomial time.”
This proof combines two ingredients: the reduction of factoring to period finding, and the demonstration that the quantum Fourier transform can find that period efficiently. The theorem formally places factoring in the class BQP (bounded-error quantum polynomial time), implying that quantum mechanics changes the landscape of computational complexity itself.
2. Reduction of factoring to order-finding
Also proven in the same 1994 paper, Shor’s order-finding theorem shows that the difficult number-theoretic task of factoring can be converted into the task of finding the order (the smallest positive integer (r) such that (a^r ≡ 1 \pmod N)). Once this order is known, the factors of (N) can be extracted with high probability.
The theorem reads conceptually as:
“Given an efficient algorithm for finding the order of a randomly chosen integer modulo N, one can find a non-trivial factor of N with high probability.”
This is the mathematical hinge that turns quantum interference into number-theoretic power. The correctness proof shows that almost any choice of a random base (a) will yield a useful order unless (a) shares a factor with N — which is already a success case.
3. Existence of good quantum error-correcting codes
In collaboration with Andrew Calderbank, Shor proved in “Good Quantum Error-Correcting Codes Exist” (arXiv:quant-ph/9512032) that it is theoretically possible to design quantum codes that protect information from noise without destroying the encoded quantum state.
The formal theorem in that paper states:
“There exist families of quantum error-correcting codes with non-zero asymptotic rate and non-zero relative distance.”
In plain language, this means we can encode qubits in a way that allows us to correct many types of errors without the exponential overhead feared by early skeptics. This result provided a rigorous mathematical foundation for quantum reliability — before it, the field was unsure if error correction was even compatible with quantum physics.
4. Fault-tolerant quantum computation
In “Fault-Tolerant Quantum Computation” (arXiv:quant-ph/9605011), Shor extended the previous result to show that large-scale, accurate quantum computation is achievable in principle.
The core theorem is expressed as:
“Arbitrary long quantum computations can be performed reliably if the error per gate, measurement, and preparation is below a certain constant threshold.”
This means there exists a numerical threshold such that, by encoding qubits redundantly and performing corrections often enough, one can make errors decay faster than they accumulate. It is the theoretical assurance that scalable quantum computing is not forbidden by physics or information theory.