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))

Quantum (Shor)

10⁹ ops

O((log N)³)

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

RESOURCE REQUIREMENTS

Target	Logical Qubits	Physical Qubits (est.)	Threat Timeline
RSA-512	~1,500	~500K	Already broken classically
RSA-2048	~4,100	<1M (Gidney, 2025)	10–25 years
RSA-4096	~8,200	~2M	15–30 years
ECC P-256	~2,330	<500K (Google, 2026)	10–20 years
ECC P-384	~3,500	~750K	15–25 years

Current largest fault-tolerant quantum computers: ~1,000 logical qubits (2026)
Gap to RSA-2048: ~4,100 logical qubits needed

▶ 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): ~2⁰ — broken in polynomial time

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 reduces collision resistance — still usable
✓ ML-KEM (Kyber) — Lattice problems — no known quantum speedup
✓ ML-DSA — Lattice problems — no known quantum speedup
✓ 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

Run the algorithm above to see a live demo.

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