Cryptography

Cryptography is the topic where quantum algorithms are easiest to overstate. Two results are doing different jobs, and this stub only connects them to the algorithm pages.

Shor's algorithm is a polynomial-time quantum algorithm for factoring and for discrete logarithms. The 1997 paper treats discrete logarithms in the multiplicative group modulo a prime. RSA is the factoring application. Finite-field Diffie–Hellman is the discrete-logarithm application in that paper. Elliptic-curve discrete logarithms are not in the 1997 theorems; Proos and Zalka show how to carry the algorithm onto elliptic curves over a prime field. A polynomial bound becomes an attack only when a machine can run the circuit. Gidney and Ekerå estimate that cost for 2048-bit RSA under stated superconducting-hardware assumptions — about 20 million noisy qubits and about 8 hours in their model. That paper is an estimate. It is the right citation when someone asks "how big," and the wrong citation for "it has been done." A different question is how much noise the Fourier rotations can absorb before the expected polynomial runtime fails. Cai and Young (2026) answer it for one relative-noise model on the small controlled rotations. The threshold, the positive-density set of primes, and the fault-tolerance remark that is not a theorem are in the digest of 12 Oct 2026.

Grover's algorithm is a quadratic reduction in the number of queries to an unstructured search oracle. Applied to exhaustive key search, it changes the security level of a symmetric primitive and does not void it. Bennett, Bernstein, Brassard, and Vazirani show that the quadratic bound is optimal for black-box search: relative to a random oracle, NP is not solvable in substantially fewer than square-root-of-the-space quantum queries. A longer symmetric key is the usual response to Grover. A post-quantum public-key migration is the response to Shor. They are not the same project.

This page does not survey post-quantum cryptosystems, protocol design, or side channels. Those subjects need their own literature. What belongs here is the separation between the two algorithms, and the habit of reading the hypothesis of each theorem before repeating the conclusion.