---
title: "Shor's Algorithm"
type: vocabulary
url: "https://www.envisioning.com/vocab/shors-algorithm"
summary: A quantum algorithm that factors integers exponentially faster than classical methods, threatening modern encryption.
year: 1994
generality: 0.70
---

# Shor's Algorithm

A quantum algorithm that factors integers exponentially faster than classical methods, threatening modern encryption.
Shor's Algorithm is a quantum algorithm that solves the integer factorization problem in polynomial time, an exponential improvement over the best known classical approaches such as the general number field sieve. Proposed by Peter Shor in 1994, the algorithm works in two conceptually distinct phases: a classical reduction that transforms factoring into the problem of finding the period of a modular exponential function, and a quantum phase that uses the quantum Fourier transform to extract that period efficiently. The quantum speedup arises because a quantum computer can evaluate the periodic function across an exponential number of inputs simultaneously through superposition, then use interference to amplify the correct period signal — a capability with no efficient classical analog.

The cryptographic implications are profound. RSA encryption and related public-key schemes derive their security from the practical intractability of factoring large integers on classical hardware. A sufficiently powerful quantum computer running Shor's Algorithm could break these systems in hours rather than the billions of years classical machines would require. This threat has driven substantial investment in post-quantum cryptography, and in 2024 NIST finalized its first set of quantum-resistant cryptographic standards partly in direct response to Shor's result.

Within machine learning and AI research, Shor's Algorithm matters primarily as a motivating example of quantum advantage — demonstrating that quantum hardware can solve certain problems in fundamentally different complexity classes than classical computers. It has shaped expectations around quantum machine learning, where researchers investigate whether similar exponential speedups might apply to optimization, linear algebra, or sampling problems central to modern AI workloads. While current quantum hardware remains too noisy and small-scale to threaten real-world encryption, Shor's Algorithm continues to define the long-term stakes of the quantum computing roadmap.

---
Source: Envisioning — Technology Research Institute (https://www.envisioning.com/vocab/shors-algorithm)