The short version

What it does
Factors large integers in polynomial time on a quantum computer.
Speedup
Runs in O((log N)^3) time, exponentially faster than classical approaches for large numbers.
What it needs
Approximately 2N qubits at minimum to factor an N-bit number, plus ancilla qubits for modular arithmetic.
The engine
The quantum Fourier transform, used to find the period of a function.
Status today
Demonstrated on toy examples such as 15 and 21. Nothing at cryptographically relevant scale.

01 How Shor's algorithm works

The algorithm is a hybrid: most of the clever quantum work reduces factoring to a period-finding problem, which a quantum Fourier transform solves efficiently. The steps, simplified:

  1. Reduce factoring to period finding Choose a random integer a that shares no factors with N (the number to factor). Consider the function f(x) = a^x mod N. This function is periodic - it repeats with some period r. If you can find r, you can often factor N using classical number theory (with high probability).
  2. Quantum Fourier Transform for period finding The quantum Fourier transform (QFT) is the engine of Shor's algorithm. It takes a superposition of function values and extracts the period exponentially faster than classical discrete Fourier transform methods.
  3. Classical post-processing Once the period r is known, classical math takes over. If r is even and a^(r/2) is not -1 mod N, then gcd(a^(r/2) +/- 1, N) yields non-trivial factors of N with high probability. If not, restart with a different random a - the algorithm succeeds quickly on average.
This is the step where quantum speedup happens: the QFT runs in O(n^2) quantum gates versus O(n * 2^n) for a classical DFT.

02 Why Shor's algorithm matters for cryptography

Modern internet security rests on the difficulty of factoring large numbers and computing discrete logarithms. Shor's algorithm solves both problems efficiently.

Vulnerable

RSA

RSA key pairs are generated from two large primes. Security depends on the difficulty of factoring their product N. Shor's algorithm factors N in polynomial time, recovering private keys from public keys.

Vulnerable

Elliptic curve cryptography

ECDSA and ECDH use the discrete logarithm problem on elliptic curves. Shor's algorithm solves the elliptic curve discrete logarithm problem too, breaking ECC-based key exchange and signatures.

Risk today

"Harvest now, decrypt later"

Adversaries can record encrypted traffic today and decrypt it once quantum computers are capable. Long-lived sensitive data - government secrets, financial records, health data - is already at risk from this strategy.

The response

Post-quantum cryptography

NIST finalized its first post-quantum standards in 2024: ML-KEM (Kyber), ML-DSA (Dilithium), and SLH-DSA (SPHINCS+). These are based on lattice and hash problems, not factoring - they remain secure against Shor's algorithm.

03 Courses covering Shor's algorithm

Quantum computing courses that include Shor's algorithm in their curriculum.

  • Prof. Elias Fernandez-Combarro Alvarez, University of Oviedo

    A Practical Introduction to Quantum Computing (CERN)

    CERN openlab's free lecture series on quantum computing covering qubits, quantum algorithms, QAOA, VQE, and quantum machine learning. Taught by a University of Oviedo professor with no physics background required.

    Self-paced (7 recorded lectures) beginner

  • edX

    Introduction to Post-Quantum Cryptography (UMBC)

    Lei Zhang (UMBC)

    UMBC's six-week edX course on post-quantum cryptography for beginning STEM learners. Lectures and labs on quantum-safe encryption, Shor and Grover, and NIST-standard algorithms. Audit is free; a verified certificate is paid.

    6 weeks, 7 hours per week beginner

  • Coursera

    Quantum Computing with Qiskit and Advanced Algorithms

    Packt

    A Qiskit-based course that moves from quantum fundamentals into the major quantum algorithms: teleportation, Deutsch, Bernstein-Vazirani, Grover's search, and Shor's factoring algorithm, with implementation on simulators and real quantum hardware.

    ~9 hours beginner

  • QWorld volunteer instructors

    QSilver: Intermediate Quantum Computing Workshop (QWorld)

    QWorld's free intermediate quantum programming workshop covering complex numbers, the quantum Fourier transform, and Shor's algorithm. The follow-on to QBronze, run as mentored online sessions through QWorld's global network.

    1 week (intensive) intermediate

  • MIT xPRO / Isaac Chuang, William Oliver, Peter Shor, Aram Harrow

    Certificate

    Quantum Computing Fundamentals (MIT xPRO)

    MIT xPRO's professional certificate program in quantum computing, taught by Isaac Chuang, William Oliver, Peter Shor, and Aram Harrow. A two-course program covering quantum computing fundamentals, algorithms for cybersecurity and chemistry, and the business implications of the technology.

    2 courses · 4 weeks each intermediate

  • Prof. Isaac Chuang and Prof. Peter Shor, MIT

    Quantum Information Science I (MIT Open Learning Library)

    MIT's three-part interactive course on quantum information science covering quantum mechanics, protocols, algorithms, and communication. Fully free with graded exercises on the Open Learning Library.

    Self-paced (3 parts) intermediate

  • Prof. Peter Shor, MIT

    Quantum Computation (MIT OpenCourseWare)

    MIT's graduate-level quantum computation course covering quantum algorithms, complexity theory, and quantum information. Lecture notes and problem sets freely available.

    Self-paced advanced

04 Shor's algorithm tutorials

Hands-on implementations and deep dives into the quantum Fourier transform and period finding.

05 Questions people ask

What is Shor's algorithm?
Shor's algorithm, developed by Peter Shor in 1994, factors large integers in polynomial time on a quantum computer. Classically, no known polynomial-time factoring algorithm exists - the best classical algorithms are sub-exponential but far slower. Shor's algorithm runs in O((log N)^3) time, making it exponentially faster than classical approaches for large numbers.
Can Shor's algorithm break RSA?
In principle, yes - with a sufficiently large fault-tolerant quantum computer. RSA relies on the hardness of factoring large semiprime numbers (products of two large primes). Shor's algorithm solves this efficiently. However, breaking 2048-bit RSA would require thousands of logical qubits with error correction. Published estimates from Google researchers put the physical qubit requirement at roughly 20 million noisy qubits (Gidney and Ekera, 2019), with a 2025 update by Gidney lowering this to under 1 million given improved techniques. Current quantum computers cannot run Shor's at cryptographically relevant scale.
How many qubits does Shor's algorithm need?
To factor an N-bit number, Shor's algorithm requires approximately 2N qubits at minimum for the quantum Fourier transform register, plus ancilla qubits for modular arithmetic. Factoring 2048-bit RSA keys would require thousands of logical qubits. With realistic error correction overhead, this translates to millions of physical qubits on current hardware architectures - far beyond what exists today.
Has Shor's algorithm been run on a real quantum computer?
Yes, but only on small toy examples. Genuine demonstrations of Shor's algorithm on quantum hardware have factored numbers like 15 and 21 - trivial cases that any classical calculator handles instantly. Claims of factoring larger numbers have generally relied on shortcuts or different methods rather than a full Shor implementation. IBM, Google, and academic groups have demonstrated the algorithm's mechanics, but not at any scale that threatens cryptography, and expert timelines for cryptographically relevant factoring still span many years to decades.
What is post-quantum cryptography?
Post-quantum cryptography (PQC) refers to classical cryptographic algorithms designed to remain secure against both classical and quantum computers. NIST published its first PQC standards in 2024: ML-KEM (based on CRYSTALS-Kyber) for key encapsulation, ML-DSA (based on CRYSTALS-Dilithium) for signatures, and the hash-based SLH-DSA (based on SPHINCS+), with additional selections following. These are not vulnerable to Shor's algorithm. Organizations are now beginning migration planning, especially for long-lived encrypted data.