Algorithm Zoo · Factoring & cryptanalysis
Shor's Algorithm (Discrete Log)
First described: Peter Shor, 1994
The problem
Given g, h, p, find x such that g^x ≡ h (mod p).
The companion algorithm to factoring, breaking the discrete-log problem that secures Diffie-Hellman and ECDSA. Same QPE machinery as factoring but with a different group operation in the unitary.
Best classical
Sub-exponential for prime fields; sub-exponential to exponential for elliptic curves
Quantum complexity
Õ(n^3) for n-bit groups; ECC over n-bit curves slightly cheaper
Our verdict
ECC was the post-RSA hope until 1994. It dies the same day RSA does. The migration math is identical: pick ML-KEM + ML-DSA today, deploy hybrid TLS, plan for a 10-year transition. Treat ECC and DH as already vulnerable for any data with a >10-year secrecy requirement.
When to use it
- Cryptanalysis modeling for any DLP-based primitive: ECDH, ECDSA, Ed25519, classical Diffie-Hellman.
- PQC threat-model work — ECC and DH fall on the same day RSA does.
When not to use it
- Anything other than cryptanalysis.
- Today's hardware. Roetteler et al. (2017): 256-bit ECDLP needs ≈2330 logical qubits — easier than RSA-2048 (≈4100 logical), still beyond reach.
Classical baseline
Pollard's rho for ECDLP is √n queries — roughly 2^128 for a 256-bit curve, infeasible classically. Quantum attack reduces to ~n^3 gates.
Hardware cost
256-bit ECDSA needs ~2330 logical qubits (Roetteler et al. 2017). With surface code at distance d=27 and 10^-3 physical error, that's ~5M physical qubits.
Key papers
- Algorithms for quantum computation: discrete logarithms and factoring ↗
Shor · 1994 · FOCS '94
- Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms ↗
Roetteler, Naehrig, Svore, Lauter · 2017 · ASIACRYPT
Deep-dive tutorials
Last verified: 2026-05-24