Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
📜 Abstract
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.
✨ Summary
Summary
Peter W. Shor develops quantum algorithms for integer factorization and discrete logarithms, problems regarded at the time as infeasible in polynomial time on classical computers and used in public-key cryptography. The central strategy is to reduce both problems to finding the period or order of a function, then use quantum interference and a quantum Fourier transform to extract information about that period.
The paper defines a quantum gate-array model based on superposition, unitary evolution, measurement, and interference. It explains how ordinary computations can be embedded reversibly into quantum circuits, including modular exponentiation, which is the principal arithmetic subroutine required by the algorithms. It also gives an efficient construction of the quantum Fourier transform for registers whose sizes are powers of two, together with an approximate version that omits sufficiently small phase rotations.
For factoring, the algorithm selects an integer (x) modulo (n), finds its multiplicative order (r) using quantum period finding, and classically derives a nontrivial factor from (\gcd(x^{r/2}-1,n)) when the order satisfies suitable conditions. The measured Fourier-transform output approximates a fraction with denominator (r); continued fractions recover candidate values of the order. The resulting quantum computation uses a number of steps polynomial in (\log n), compared with the subexponential classical methods known at the time.
For discrete logarithms, the paper prepares a superposition over two exponents, computes a relation involving (g^{ax-b}), applies Fourier transforms to both exponent registers, and uses the measurement statistics to recover the unknown exponent through modular arithmetic and the Chinese remainder theorem. The approach extends beyond the particular groups used in the main presentation to other groups with efficiently computable multiplication, inversion, and suitable cyclic structure.
The paper also discusses implementation constraints, especially reversibility, gate precision, decoherence, workspace, and error accumulation. It does not claim that quantum computers were then available; rather, it establishes that, under the quantum circuit model, factoring and discrete logarithms belong to quantum polynomial time with bounded error.
Influence
The result became a foundational target for experimental quantum-computing research. Subsequent work demonstrated compiled or restricted instances of the algorithm, including photonic implementations and nuclear-magnetic-resonance experiments, while later work addressed formally verified end-to-end implementations of general Shor circuits. (journals.aps.org)
Its cryptographic consequence is that sufficiently large fault-tolerant quantum computers would threaten public-key systems based on factoring and discrete logarithms, including RSA and related schemes. This threat directly motivated post-quantum cryptography research and standardization; NIST reports that its finalized post-quantum standards are intended to replace vulnerable public-key mechanisms before cryptographically relevant quantum computers become available. (nvlpubs.nist.gov)
The paper’s concrete influence is therefore visible in two connected lines of work: the development of quantum algorithms and architectures capable of implementing period finding, and the migration of cryptographic infrastructure toward algorithms designed to resist quantum attacks.