Cryptography

An exponential speedup for factoring and discrete log, killing RSA and ECC; and only a square root for unstructured search, which is why symmetric crypto survives...

Convince someone you know a secret while revealing nothing. The most counterintuitive constructive result in the series.

All of modern crypto rests on an unproven assumption. Why P != NP would still not be enough to secure anything.

Security lives in the key; and Shannon's proof that the one-time pad is unbreakable and impractical for the same reason.

O(log n) proof that one item belongs to a huge set. Git, certificate transparency, and every blockchain are the same data structure.

Interaction plus randomness lets a prover convince you of things you could never check alone.

An unknown quantum state cannot be copied, and the two-line proof is just linearity.

Collisions arrive at sqrt(N), not N. Sets every hash length, UUID size, and nonce width you will ever choose.