Shor's algorithm: the one quantum algo that ends RSA/ECC tomorrow

Summary

1. Introduction: The Algorithm That Broke the Future Peter Shor writes a few pages of math. The entire world’s public-key cryptography dies on those pages. RSA. Diffie-Hellman. Elliptic Curve crypto. All of it collapses the moment someone runs Shor’s algorithm on a big enough quantum machine. This isn’t Grover’s “square-root speedup” that just makes brute force a bit faster. This is exponential turned into polynomial. Game over. Governments already record encrypted traffic today betting on Shor tomorrow. Your cloud backups, your TLS sessions, your Bitcoin private keys. All harvestable now, decryptable later. Shor’s algorithm is not a future threat. It is a retroactive one. 2. The Core Problem: Factoring and Discrete Logs Today’s internet runs on two “hard” problems: Factoring: given a giant number N = p × q, find p and q. → RSA lives here. Discrete logarithm: given g^x mod p (or a point multiplication on an elliptic curve), find x. → DH, ECDH, ECDSA live here. Classical computers suck at both. Best attacks are sub-exponential and painfully slow for 2048-bit numbers. Quantum computers with Shor don’t care. Theorem (The RSA Problem) RSA Security Assumption: Given a modulus N=p⋅qN = p \cdot qN=p⋅q where ppp and qqq are large prime numbers, and given the public exponent eee and ciphertext ccc, it is computationally infeasible for a classical computer to recover the plaintext mmm from ce≡m(modN)c^e \equiv m \pmod{N}ce≡m(modN) without knowing the private exponent ddd.Mathematical Statement: The RSA problem reduces to factoring: if you can factor NNN, you can compute ϕ(N)=(p−1)(q−1)\phi(N) = (p-1)(q-1)ϕ(N)=(p−1)(q−1) and derive d=e−1(modϕ(N))d = e^{-1} \pmod{\phi(N)}d=e−1(modϕ(N)). Theorem (The Discrete Logarithm Problem) Discrete Logarithm Assumption: Given a generator ggg of a finite group GGG of prime order ppp, and given h=gx(modp)h = g^x \pmod{p}h=gx(modp), it is computationally infeasible to find the exponent xxx.Mathematical Statement: For h=gx(modp)h = g^x \pmod{p}...