# Peter Shor

> 1959– · Mathematician
>
> **Recorded contribution:** Shor's algorithm — quantum factoring in polynomial time; quantum error correction

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Peter Shor discovered in 1994 that a fault-tolerant quantum computer could factor integers and compute discrete logarithms in polynomial time, threatening widely used public-key assumptions. He also contributed quantum error-correcting codes, helping address the physical fragility exposed by such powerful algorithms. This work asks what computation becomes possible when state and measurement follow quantum rather than classical rules. The chronology is used causally: it connects the inherited constraint to an implementable mechanism and then to later reuse, instead of treating fame, job title, or eventual market success as the explanation.

## 2. The problem inherited

No efficient classical algorithm was known for factoring large general integers, yet RSA security relied on that practical difficulty; quantum computing lacked an algorithm demonstrating an economically consequential asymptotic advantage. A quantum speedup requires more than parallel-sounding language: the algorithm must prepare amplitudes, transform their phases, exploit interference, and extract limited classical information by measurement.

## 3. The central contribution

Shor’s algorithm reduces factoring to period finding, prepares a superposition of inputs, evaluates modular exponentiation coherently, applies a quantum Fourier transform, and infers a period from measured samples. The contribution is an explicit quantum model, algorithm, or systems vocabulary that states both the advantage and the physical assumptions required.

## 4. Reconstruct the mechanism

1. Choose a composite integer and a coprime base whose modular powers have a hidden period. Write the relevant basis states, amplitudes, oracle or channel, and measurement target.
2. Prepare a superposition and compute modular exponentiation without measuring the input register. Execute the unitary or protocol steps on the smallest nontrivial instance.
3. Apply the inverse quantum Fourier transform so amplitudes concentrate near multiples related to the period. Show where constructive and destructive interference change outcome probabilities.
4. Use continued fractions and greatest common divisors classically; record cases that yield no factor and must be repeated. Add noise, limited qubits, repeated measurement, or an unsuitable problem structure and explain what happens to the claimed advantage.

## 5. What changed downstream

- The algorithm launched major investment in quantum computing, post-quantum cryptography, resource estimation, and fault tolerance.
- The work gave the field algorithms and limits against which hardware, error correction, and classical alternatives could be evaluated.
- The transferable first-principles lesson is to separate the artifact named in “Shor's algorithm — quantum factoring in polynomial time; quantum error correction” from the mechanism, surrounding institution, and evidence that allowed later systems to depend on it.

## 6. Attribution, limits, and uncertainty

- Polynomial time does not mean near-term feasibility: useful RSA-scale attacks require error-corrected logical qubits, deep circuits, and enormous physical resources. Factoring history includes many classical and quantum contributors, and Shor’s error-correction work is distinct from the factoring algorithm.
- Asymptotic advantage does not imply near-term practicality; encoding, fault tolerance, constants, and classical preprocessing must be counted.
- The subject is living or the registry has no death year; current titles and institutional affiliations are treated as dated snapshots verified on 2026-08-09, not permanent identity claims.

## 7. Reconstruction lab

Execute period finding for 15 with a simulator or hand table. Derive candidate factors, count logical operations, then explain which steps dominate on a fault-tolerant machine. Use a state-vector or circuit simulator and compare the quantum trace with the best simple classical method for the same tiny input.

## 8. Evidence trail

- [Algorithms for quantum computation: discrete logarithms and factoring](https://doi.org/10.1109/SFCS.1994.365700) — IEEE
- [Peter Shor](https://en.wikipedia.org/wiki/Peter_Shor) — Wikipedia contributors · overview and bibliography
- [Peter Shor structured identity record](https://www.wikidata.org/wiki/Q370071) — Wikidata contributors · CC0

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*