Shor's Algorithm Explained: How a Quantum Computer Breaks RSA Encryption

Shor's algorithm is the reason Q-Day exists. Invented by mathematician Peter Shor in 1994 — more than a decade before a quantum computer capable of running it existed — it describes exactly how a quantum computer can factor large numbers exponentially faster than any classical machine. Since RSA encryption, the security standard protecting most of the internet, derives its strength from the difficulty of factoring large numbers, Shor's algorithm is the direct threat. Understanding it is understanding why the cryptographic migration currently underway is not optional.

Why RSA depends on factoring being hard

RSA encryption works because of a mathematical asymmetry: it is trivial to multiply two large prime numbers together, but extraordinarily difficult to factor the result back into its components. Generating an RSA key pair takes a fraction of a second. Breaking it by finding the prime factors of the resulting 2048-bit number would, on the fastest classical supercomputer using the best known classical algorithm, take longer than the current age of the universe.

This asymmetry is not a gap waiting to be closed with faster hardware — it is a structural property of the mathematical problem. The best classical factoring algorithms (the General Number Field Sieve) have sub-exponential but still enormous complexity. Adding more classical computing power reduces the time but never enough to be practical. This is why RSA has been considered secure for 50 years. Shor's algorithm breaks the asymmetry entirely.

The key insight: factoring is periodic

Shor's central insight was that the problem of factoring a number N can be reduced to a different problem: finding the period of a mathematical function. Specifically, for a randomly chosen number a (less than N), the function f(x) = aˣ mod N is periodic — it cycles through values and eventually repeats. If you can find the period r of this function, you can use it to compute the factors of N using classical mathematics. The factoring problem becomes a period-finding problem.

This matters because finding a period is exactly the kind of problem that quantum computers solve efficiently. Classical computers must evaluate the function at each value of x one at a time to find the period — an exponentially long process for large N. A quantum computer can evaluate the function at all possible values of x simultaneously using superposition, then use the Quantum Fourier Transform to extract the period from the interference pattern.

How Shor's algorithm works, step by step

Choose a random number a smaller than N (the number to be factored). Check with classical computation whether a shares a common factor with N — if so, the factoring is already done. In practice this is almost never the case for large RSA numbers.

Create a superposition of all possible input values using Hadamard gates on the input register. The quantum register now simultaneously holds every value from 0 to 2ⁿ-1 — all possible guesses at once.

Compute the function f(x) = aˣ mod N across the entire superposition simultaneously using a quantum circuit. Because the input register is in superposition, the output register now contains all possible outputs of f at once — entangled with the corresponding inputs.

Apply the Quantum Fourier Transform (QFT) to the input register. The QFT converts the periodic pattern in the quantum state into a probability distribution that peaks at multiples of 1/r — where r is the period of f. This is the quantum step that has no classical equivalent at this scale.

Measure the result. The measurement yields a value close to k/r for some integer k. Repeat a small number of times to determine r precisely using classical continued fraction techniques.

Compute the factors classically using r. If r is even and a^(r/2) ≢ −1 (mod N), then gcd(a^(r/2) ± 1, N) yields the prime factors of N. If not, repeat from step 1 with a different a — this succeeds with high probability after a small number of attempts.

Why the Quantum Fourier Transform is the key

The classical Discrete Fourier Transform applied to N data points takes O(N log N) operations. The Quantum Fourier Transform does the equivalent computation in O((log N)²) quantum gate operations — an exponential speedup. For a 2048-bit RSA number, the difference between these complexities is what separates "longer than the universe" from "hours." The QFT is not magic — it is quantum interference applied systematically: the algorithm is designed so that values that are multiples of the period interfere constructively, while all other values interfere destructively, leaving the measurement overwhelmingly likely to reveal the period.

The speedup in numbers

Factoring a 2048-bit RSA number classically using the General Number Field Sieve requires approximately 10³⁴ operations — more than the number of atoms in the Earth. Shor's algorithm requires approximately 10¹² quantum gate operations — a ratio of roughly 10²². That is not a quantitative improvement; it is a qualitative change in what is computable.

How many qubits does it actually require?

In 1994, when Shor published his algorithm, the resource estimates for running it against RSA-2048 were enormous. The 2019 estimate from Google researcher Craig Gidney put the requirement at roughly 20 million physical qubits. In May 2025, Gidney published a revised paper showing the same computation could be done with under one million physical qubits — a 20× reduction enabled by more efficient circuit designs and improved error correction techniques. A further paper from the AQTI research group in March 2026 suggested even lower resource requirements are achievable. The trend is clear: the qubit threshold is falling faster than the qubit count is rising.

Current quantum computers — Google's 105-qubit Willow, IBM's Flamingo-class systems, China's 180-qubit Wukong-180 — are nowhere near the threshold. But they are not the endpoint. The same hardware trajectories that went from 50 qubits in 2019 to over 1,000 in 2023 are continuing. The question is not whether a machine capable of running Shor's algorithm against RSA-2048 will be built — it is when. Google's internal security team plans for 2029. The Global Risk Institute puts a 28–49% probability on this decade.

What Shor's algorithm does and does not break

Shor's algorithm specifically threatens RSA and elliptic curve cryptography (ECC) — both of which depend on mathematical problems (integer factoring and discrete logarithms) that Shor can solve efficiently. It does not directly break symmetric encryption like AES. A separate quantum algorithm, Grover's algorithm, can search an unsorted database quadratically faster than classical methods — effectively halving the security level of a symmetric key. AES-256 drops to roughly AES-128 equivalent security against a quantum adversary, which is still considered secure.

The practical implication: every HTTPS connection, certificate authority, VPN, code signature, and cryptocurrency wallet that relies on RSA or ECC is theoretically vulnerable to a quantum computer running Shor's algorithm. NIST's post-quantum standards — ML-KEM, ML-DSA, FN-DSA, and SLH-DSA — are designed as quantum-resistant replacements, based on mathematical problems (lattice problems, hash functions) for which no quantum speedup equivalent to Shor's is known to exist. Migrating to these standards before a cryptographically relevant quantum computer arrives is the entire Y2Q challenge.