Shor’s Algorithm
Shor’s algorithm is a quantum algorithm discovered by mathematician Peter Shor in 1994 that solves integer factorisation and discrete logarithm problems — including the Elliptic Curve Discrete Logarithm Problem (ECDLP) — in polynomial time. On a classical computer these problems are believed to be computationally intractable; Shor’s renders them tractable on a sufficiently powerful quantum computer.
Why It Matters
Most current public-key cryptography (RSA, ECC) bases its security on the assumption that factoring large numbers or solving discrete logarithms is practically impossible classically. Shor’s algorithm eliminates that assumption on quantum hardware — directly threatening:
- bitcoin and blockchain wallet security (ECDLP-256)
- RSA-encrypted internet communications (TLS/HTTPS)
- Many other public-key systems
Recent Resource Optimisations
Running Shor’s on ECDLP-256 for bitcoin requires specific quantum circuit compilation. Recent advances have dramatically reduced the resource requirements:
| Source | Physical Qubits Required | Key Development |
|---|---|---|
| Prior estimates (pre-2026) | Millions | Early CRQC estimates |
| babbush-neven-2026-quantum-vulnerabilities-cryptocurrency (Google, 2026) | < 500,000 | ~20× reduction; two circuit variants |
| Combined Google + Caltech (cottier-2026-quantum-computing-breakthroughs) | ~25,000–30,000 | Caltech fault-tolerance scheme reduces overhead further |
scott-aaronson: “A year ago, the best estimate would have been in the millions.”
Google published their circuit details via a zero-knowledge proof — verifiable without providing an attack roadmap (babbush-neven-2026-quantum-vulnerabilities-cryptocurrency).
Implications
The rapid drop in required qubit count — from millions to potentially 25,000–30,000 — means the window for PQC migration is much shorter than previously assumed. The bitcoin network and most other blockchain systems must upgrade their cryptographic foundations before cryptographically relevant quantum computers exist.
Sources
- babbush-neven-2026-quantum-vulnerabilities-cryptocurrency — Updated Google circuit estimates; responsible disclosure via ZK proof
- cottier-2026-quantum-computing-breakthroughs — Combined qubit implications; Aaronson commentary