Shor, Grover, and a realistic view of Q-day
Two algorithms define the quantum threat to cryptography. One is existential for public-key crypto; the other is manageable.
"Q-day" is shorthand for the day a cryptographically relevant quantum computer (CRQC) exists. Two algorithms decide what it breaks.
Shor's algorithm: public-key crypto falls
Shor finds the period of a function in polynomial time. That solves integer factoring (RSA) and discrete logarithms, including on elliptic curves (ECDH, ECDSA, Schnorr). Every widely deployed public-key scheme today relies on one of these problems.
Grover's algorithm: symmetric crypto bends
Grover gives only a quadratic speedup for unstructured search, so a 256-bit key offers roughly 128 bits of quantum security. Doubling key sizes is enough: AES-256 and SHA-256 remain sound.
How far away is it?
- Resource estimates have fallen sharply: a 2025 estimate by Gidney puts RSA-2048 at under one million noisy physical qubits running for about a week.
- Elliptic-curve discrete logs at 256 bits need on the order of a few thousand logical qubits, each built from many physical qubits through error correction.
- Data harvested today can be decrypted later ("harvest now, decrypt later"), so key exchange needs to migrate before signatures do.
Our quantum-lab package simulates both algorithms on toy inputs so anyone can see the mechanics for themselves.