Shor's Algorithm

Why RSA trusts factoring to be hard

RSA encryption rests on a single asymmetry: multiplying two large primes together is fast, but recovering those primes from the product is, as far as anyone has proven classically, extremely slow. Generate two large primes p and q, publish their product N = p·q as the modulus, and keep p and q secret. The private key is derived from φ(N) = (p−1)(q−1), which nobody outside the key holder can compute without factoring N first. Peter Shor's 1994 algorithm was the first polynomial-time algorithm — quantum or classical — for this exact problem, and it is the reason RSA-2048 and elliptic-curve cryptography are considered at risk from a sufficiently large quantum computer.

best classical factoring (GNFS):  time ≈ exp(N^(1/3))         for RSA-2048: ~10²³ operations
Shor's algorithm:                 time ≈ O(n³) quantum gates    for RSA-2048: ~10¹⁰ operations

That ten-orders-of-magnitude gap between exponential and polynomial scaling — not a faster brute-force search, but a structurally different algorithm — is what makes Shor's Algorithm such a landmark, and why simulating even a small instance of it, as the interactive demo on this site does, is worth doing by hand.

The reduction: factoring is period finding in disguise

Shor's real insight was not a faster way to search for factors directly — it was noticing that factoring N reduces to finding the order of a randomly chosen element in the multiplicative group modulo N. Pick a random a with 1 < a < N and gcd(a,N) = 1 (if the gcd isn't 1, you have already stumbled onto a factor classically, no quantum computer needed). The sequence a¹, a², a³, ... mod N is periodic; call its period r — the smallest positive integer with aʳ ≡ 1 (mod N). If r happens to be even and a^(r/2) is not congruent to −1 mod N, elementary algebra hands you a factor for free.

a^(r/2) ≡ 1 (mod N)  ⟹  (a^(r/2) − 1)(a^(r/2) + 1) ≡ 0 (mod N)

worked example:  N = 15, a = 7
  7¹=7, 7²=4, 7³=13, 7⁴=1 (mod 15)  →  order r = 4
  a^(r/2) = 7² = 49 ≡ 4 (mod 15)
  gcd(4−1, 15) = gcd(3, 15) = 3      ✓ factor found
  gcd(4+1, 15) = gcd(5, 15) = 5      ✓ other factor found

Finding that order classically is itself hard — baby-step giant-step search costs O(√r), still exponential in the number of bits — so this reduction alone buys nothing without a fast way to find r. That is exactly the piece a quantum computer supplies.

The quantum Fourier transform reads off the period

The quantum Fourier transform (QFT) is the quantum cousin of the discrete Fourier transform: instead of transforming a list of classical numbers, it transforms the amplitudes of a superposition of quantum basis states. On n qubits it needs only n Hadamard gates and n(n−1)/2 controlled-phase rotations — O(n²) gates total, versus O(n·2ⁿ) for a classical DFT over the same 2ⁿ-element space. The property that makes it useful here: feed the QFT a superposition whose amplitudes are periodic with period r, and the output amplitudes concentrate sharply near multiples of N/r, which measurement can then reveal.

Shor's quantum subroutine puts this to work with two registers. A control register is put into a uniform superposition over every value x from 0 to N−1 with n Hadamard gates. A modular exponentiation circuit then computes aˣ mod N into a target register — for every x in the superposition simultaneously, courtesy of quantum parallelism — using O(n³) gates built from repeated squaring. Measuring the target register collapses it to one value, which in turn collapses the control register into a superposition of exactly the x-values that produce that value: a state periodic in x with period r. Apply the QFT to that periodic superposition and measure again, and the outcome c is very likely to be close to some integer multiple of N/r.

From a noisy measurement back to the exact period

The QFT hands back an approximation, c ≈ k·N/r for some unknown integer k — not r itself. Recovering the exact period from c/N is a classical problem solved by continued fraction expansion: writing c/N as a continued fraction and reading off its convergents p/q gives the best rational approximations to c/N with small denominators, and whenever |c/N − k/r| < 1/(2N), one of those convergents equals k/r exactly, exposing r (or a small multiple of it that a follow-up check resolves).

A single run succeeds with probability roughly 1/(2 ln r) ≈ 1/n, so the whole circuit — Hadamards, modular exponentiation, QFT, measurement, continued fractions, gcd — is expected to run about O(n) times before it produces a usable factor. Every step outside the QFT and modular exponentiation runs on an ordinary classical computer; the quantum hardware is only doing the period-finding heavy lifting.

How many qubits RSA-2048 actually needs

Factoring an n-bit number needs on the order of 2n + 3 logical qubits — about 4,000 for RSA-2048's 2048-bit modulus — running roughly 10¹⁰ quantum gates. The gap between logical and physical qubits is where the real difficulty hides: surface-code error correction, the leading fault-tolerant scheme, needs on the order of 1,000 noisy physical qubits per clean logical qubit, putting RSA-2048 at roughly 4 million physical qubits. The largest processors built as of 2026 run in the low thousands of physical qubits — Google's Willow and IBM's Condor-class devices among them — so a cryptographically relevant factoring run remains a hardware problem measured in years to decades, not a software problem waiting on a better algorithm.

Why the migration to post-quantum cryptography is happening now anyway

The distance to a working large-scale quantum computer is exactly why organizations aren't waiting for one to be built. Encrypted traffic captured today can simply be stored and decrypted later once the hardware exists — a "harvest now, decrypt later" attack that only threatens data that still needs to be secret years from now. NIST finalized its first post-quantum cryptography standards in 2024 after a six-year public evaluation: ML-KEM (formerly CRYSTALS-Kyber) for key exchange, ML-DSA (formerly Dilithium) for signatures, plus SLH-DSA and FN-DSA as alternatives built on different hard problems. Both rely on lattice or hash-based problems believed to resist quantum attack, unlike RSA's factoring problem. Major browsers and CDN providers have already deployed hybrid schemes that run a classical algorithm and a post-quantum one side by side, so today's connections stay protected even if one of the two approaches is eventually broken.

Frequently asked questions

Try it live

Everything above runs in your browser — open Shor's Algorithm and step through order-finding for N = 15, 21, 35 or 91 to watch the period, the QFT peaks and the extracted factors appear stage by stage. Nothing is installed, nothing is uploaded, the whole model lives in one tab.