Key Takeaways: Chapter 15 — Shor's Algorithm — Factoring Large Numbers in Polynomial Time (and Why It Breaks RSA Encryption)

• Factoring reduces to period finding: Given $a$ coprime to $N$, the period $r$ of $f(x) = a^x \bmod N$ reveals factors of $N$ via $\gcd(a^{r/2} \pm 1, N)$.

• Quantum speedup comes from the QFT: The quantum Fourier transform extracts the period $r$ in $O((\log N)^2)$ gates, compared to the exponential classical cost of directly searching for $r$.

• Modular exponentiation is the bottleneck: Implementing $a^x \bmod N$ as a quantum circuit requires $O((\log N)^3)$ gates, dominating the overall complexity.

• Continued fractions bridge quantum and classical: The phase estimate $c/2^t \approx k/r$ is converted to the exact rational $k/r$ via the classical continued fraction algorithm.

• Shor's algorithm breaks RSA and ECC: Any quantum computer with $\sim 10^4$–$10^7$ logical qubits can factor RSA moduli and compute discrete logarithms, motivating the transition to post-quantum cryptography.

• Quantum is linear algebra, not magic: The algorithm exploits the linearity of quantum mechanics (superposition and unitary evolution) and the structure of the Fourier transform to extract periodicity — a purely algebraic property.

• Noise is the enemy: The exponential resource requirements for factoring cryptographically relevant integers highlight why error correction is essential for practical quantum advantage.

• We're at the beginning: Current demonstrations factor only $N = 15, 21$ — trivial classically. Factoring RSA-2048 remains decades away.