Shor's Algorithm

Quantum period-finding · QFT · continued fractions

Factor an integer N by turning it into quantum order-finding: extract the period of a mod N via the QFT and continued fractions, then recover the factors with gcd(a^(r/2)±1, N).

What is Shor's Algorithm?

Back in 1994, mathematician Peter Shor had a brilliant insight: a quantum computer could factor large numbers exponentially faster than any classical method. It's one of the most dazzling results in computer science — and the spark that launched the whole field of post-quantum cryptography.

The problem it solves

Split a big integer N back into its prime building blocks. For a 2048-bit number, the best classical algorithm (GNFS) would chew on it for billions of years — Shor's algorithm wraps it up in hours. 🚀

Why it's a big deal

RSA, ECC, and Diffie-Hellman — the encryption guarding nearly every website, bank, and message — all lean on factoring being hard. Shor's algorithm flips that on its head, and that's exactly why it's so exciting to explore.

The clever trick

Here's the magic: Shor reframes factoring as a period-finding puzzle, then lets a quantum Fourier transform spot that period in a single elegant shot. Fire up the demo below and watch it unfold step by step!

Factor N:

Presets:

Shor is randomized: each run picks a fresh base a and can fail and retry. Try N = 21 or 91 and run it several times — watch the base, the period, and the retry path change every time.

Why does the period r let you factor N?

Pick a base a and look at its order r — the smallest power with a^r ≡ 1 (mod N). That one fact is a factoring machine:

a^r ≡ 1 means a^r − 1 ≡ 0 (mod N).
If r is even, factor the left side as a difference of squares: (a^r/2 − 1)(a^r/2 + 1) ≡ 0 (mod N).
So N divides that product. Unless a^r/2 ≡ ±1 (the two dead-ends the demo retries past), N's prime factors must split between the two factors — so each shares a real factor with N.
Peel them off with the fast, classical gcd(a^r/2 ± 1, N).

This run: run the algorithm and the exact numbers from your factorisation appear here.

The quantum computer's only job is finding r. Everything above is ordinary arithmetic — which is why the whole attack collapses to "find the period fast."

Why does the QFT concentrate at multiples of Q/r?

After order-finding, the register holds every input x that shares one f(x) = a^x mod N value — an evenly spaced comb x₀, x₀+r, x₀+2r, … The QFT gives each state a phase that spins as a clock hand, at a rate set by the frequency m you might measure.

At a frequency m where m·r/Q is a whole number, every hand in the comb points the same way — they add up (constructive interference). That happens exactly at m = k·Q/r.
At any other m the hands fan out around the circle and cancel (destructive interference) — near-zero probability.

So a single measurement almost always lands on a spike at k·Q/r. The phasor wheels below animate exactly this — watch the hands align at the period and scatter off it. (classically simulated)

Enter N and press ▶ Run Shor's Algorithm to begin.

Visualization will appear here after running the algorithm.

FACTORING COMPLEXITY AT RSA-2048

Classical (GNFS)

10³⁴ ops

exp(O((log N)^1/3(log log N)^2/3))

Quantum (Shor)

10⁹ ops

O((log N)³)

Bars are on a log₁₀ axis (length ∝ number of digits in the op count). The 25-unit gap between them is a factor of ~10²⁵× — twenty-five orders of magnitude, not the 2–3× a linear bar would suggest.

The classical bar is the conservative anchor: NIST (SP 800-57 Part 1 Rev. 5) rates RSA-2048 at 112-bit security, i.e. 2¹¹² ≈ 5 × 10³³ operations. Evaluating the GNFS cost function itself — L_N[1/3, 1.923] = exp(81) for a 2048-bit N — gives ≈ 10³⁵ (≈ 2¹¹⁷). Both land in the 10³⁴–10³⁵ band, so 10³⁴ is plotted; the real gap is 25 orders of magnitude or more.

Dated quantum resource estimates

Target and estimate	Logical qubits	Physical qubits	Estimated runtime
RSA-2048 — Gidney–Ekerå, 2019 preprint / 2021 publication	Separate circuit account; not taken from the 2025 estimate	20 million noisy qubits	8 hours
RSA-2048 — Gidney, 21 May 2025, §3.2	1,409 active; 1,537 including idle hot patches	897,864 before slack; approximately one million with safety slack	Less than one week

These are conditional resource estimates, not executed RSA-2048 attacks or dates for a future quantum computer. The 2025 design trades space for time using approximate residue arithmetic, yoked cold storage and magic-state cultivation. Both estimates assume nearest-neighbor connectivity, 0.1% uniform gate error, 1 μs surface-code cycles and 10 μs control reaction time. Logical and physical counts from different circuit designs must not be combined into one estimate.

Neutral-atom architecture experiment (online 10 November 2025; January 2026 issue): the up-to-96-logical-qubit result is a postselected distance-4 cluster-state experiment (Fig. 6), distinct from the paper’s non-postselected surface-code QEC experiments. It is not a 96-qubit cryptanalytic computer, and its task, code distance and postselection prevent a simple qubit-count comparison with the factoring estimates.

▶ Why Shor breaks ECC too

Shor's algorithm also solves the discrete logarithm problem — the mathematical foundation of ECC and Diffie-Hellman.

ECC P-256 security (classical): 2¹²⁸ operations

ECC P-256 security (quantum): no exponential margin left — the cost drops to a polynomial in the key length (~10⁹ quantum gates), not an exponential in it

ECDH, ECDSA, and all ECC-based protocols are equally vulnerable. Smaller key sizes make ECC faster to break than RSA on a quantum computer.

QUANTUM-RESISTANT AFTER SHOR

✓ AES-256 — Grover reduces to 128-bit effective — still strong
✓ SHA-3 — Grover halves preimage resistance (SHA3-256 → ~2¹²⁸) — still usable
✓ ML-KEM (Kyber) — Lattice problems — no known efficient quantum attack
✓ ML-DSA — Lattice problems — no known efficient quantum attack
✓ SLH-DSA — Hash-based — quantum-safe by design
✓ BB84 QKD — Physics-based — immune to all computational attacks
✗ RSA (any size) — Broken by Shor
✗ ECC (any curve) — Broken by Shor
✗ Diffie-Hellman — Broken by Shor

“No known efficient quantum attack” is the precise claim for the lattice schemes — not “no quantum speedup at all.” Grover-accelerated lattice sieving does shave a sub-exponential factor off the best known attack, which is why NIST’s ML-KEM/ML-DSA parameter sets already price a quantum sieve in. What no one has is a polynomial-time quantum algorithm for the underlying lattice problems, the way Shor is one for factoring.

Run the algorithm above to see a live demo.

→ crypto-lab-kyber-vault — post-quantum replacement
→ crypto-lab-bb84 — physics-based alternative