What Is Shor’s Algorithm?

This is part of the Quantum Security Reference Deep Dive series. For the full landscape overview, see the capstone article on quantum security.

Introduction

Shor’s algorithm is a quantum algorithm that efficiently factors large integers and computes discrete logarithms, the two mathematical problems that underpin RSA, Elliptic Curve Cryptography (ECC), and Diffie-Hellman key exchange. Published by mathematician Peter Shor in 1994, it proved that a quantum computer could break the public-key cryptography protecting virtually all digital communications. Shor’s algorithm is the reason post-quantum cryptography (PQC) exists.

What It Does

Classical computers struggle with certain mathematical problems that grow exponentially harder as the numbers get larger. Factoring the product of two large prime numbers is one of them. RSA encryption depends on this difficulty: multiplying two 1,024-bit primes together is trivial, but recovering those primes from the product is computationally infeasible for any classical machine. The best classical factoring algorithms would take longer than the age of the universe to break RSA-2048.

Shor’s algorithm changes the complexity class of this problem. On a quantum computer, it reduces integer factorization from exponential time to polynomial time, meaning the problem becomes tractable rather than impossible. The same applies to the discrete logarithm problem, which protects ECC and Diffie-Hellman.

The implications for cybersecurity are total. RSA key exchange, ECDH key agreement, RSA signatures, ECDSA signatures, Diffie-Hellman negotiation in VPNs and TLS: all of it falls to a single algorithm. I cover the specific impact on each cryptographic family in my analysis of how ECC became the easiest quantum target.

What It Needs

Shor’s algorithm cannot run on today’s quantum hardware. It requires a fault-tolerant quantum computer with enough error-corrected logical qubits to sustain a computation over millions of operations without accumulating fatal errors. The machine that meets this threshold is called a Cryptographically Relevant Quantum Computer (CRQC).

The resource estimates for building a CRQC have been a moving target, and they have moved consistently in one direction.

In 2021, the best published estimate (Gidney and Ekerå) concluded that breaking RSA-2048 would require approximately 20 million physical qubits and roughly eight hours of computation. In May 2025, Gidney published an updated analysis that brought the requirement below one million physical qubits with a runtime of under one week. That 20× reduction came entirely from algorithmic and error correction improvements, not from any change in hardware assumptions. The physical error rates, qubit connectivity, and gate speeds were the same; the algorithm simply uses the machine more efficiently.

ECC may fall with even fewer resources. The Chevignard, Fouque, and Schrottenloher paper presented at EUROCRYPT 2026 estimated that breaking the P-256 curve (the most widely deployed ECC standard) requires only 1,193 logical qubits. In March 2026, Google’s quantum team published research suggesting that fewer than 500,000 superconducting physical qubits could break ECC-256 in under nine minutes.

For context, the largest gate-based quantum computers today operate with a few thousand physical qubits, and their error rates are orders of magnitude above what Shor’s algorithm requires. The gap is real. But five years ago, the gap was 20× larger.

What It Has Actually Achieved

Shor’s algorithm has been demonstrated on real quantum hardware, but only for trivially small numbers. The largest integers factored using Shor’s on a genuine quantum computer are 15 and 21. I maintain a detailed analysis of why “they’ve only factored 15” is the wrong way to judge quantum computing progress, and a companion piece examining the enormous gap between factoring a 48-bit number and cracking RSA-2048.

The point is not that these demonstrations are impressive. They are not, in isolation. The point is that the theoretical algorithm is proven, the resource estimates are being refined and reduced with every new paper, and the engineering trajectory of quantum hardware is pointed at eventually closing the gap. The question for security planners is not whether Shor’s algorithm works (it does, mathematically). The question is how quickly the hardware will catch up.

What It Does Not Threaten

Shor’s algorithm is specific. It breaks mathematical problems with a particular algebraic structure: integer factorization and discrete logarithms over finite groups. It does not threaten symmetric cryptography (AES), hash functions (SHA-256, SHA-3), or the new PQC algorithms standardized by NIST, which are built on different mathematical foundations (lattice problems, hash-based constructions, error-correcting codes).

Grover’s algorithm is the quantum threat to symmetric cryptography, and its impact is far less severe: it halves effective key lengths, meaning AES-256 retains roughly AES-128 equivalent security. The existential threat to modern cryptography comes from Shor’s, not Grover’s.

What This Means for Your Organization

If your systems use RSA, ECC, or Diffie-Hellman (and they almost certainly do), Shor’s algorithm is the reason you need to migrate to post-quantum cryptography. The HNDL threat means that data encrypted with these algorithms today is already at risk of future decryption. The TNFL threat means that digital signatures made today could be forged retroactively.

My CRQC Quantum Capability Framework tracks the engineering progress toward the machine that will run Shor’s at scale. The PQC Migration Framework provides the methodology for defending against it.

Go Deeper

Breaking RSA-2048 with 20M Qubits — the 2021 baseline for comparison

Shor’s Algorithm: A Quantum Threat to Modern Cryptography — full technical deep dive

How ECC Became the Easiest Quantum Target — Shor’s impact across RSA, ECC, and Diffie-Hellman

Quantum Breakthrough for RSA-2048 (Gidney 2025) — the latest resource estimate

Algorithm-Level Quantum Threat to ECC (EUROCRYPT 2026) — P-256 at 1,193 logical qubits

Google Quantum vs. Bitcoin ECDLP — ECC-256 under 500K qubits

What Is a CRQC? — the machine Shor’s algorithm needs