Shor's Algorithm: Breaking Classical Cryptography

Introduction

Shor's algorithm, formulated by Peter Shor in 1994, is a quantum algorithm for finding the prime factors of an integer $N$. On a classical computer, factoring large integers is believed to be computationally intractable, forming the security foundation of modern encryption (RSA).

Complexity Comparison

• Classical: The best-known classical algorithm is the General Number Field Sieve (GNFS), which operates in sub-exponential time: $\mathcal{O}\left(\exp\left(c \sqrt[3]{\ln N (\ln \ln N)^2}\right)\right)$
• Quantum: Shor's algorithm solves the problem in polynomial time: $\mathcal{O}((\log N)^3)$

How It Works

Shor's algorithm reduces the factoring problem to a period-finding problem on a group, which can be solved efficiently using a quantum computer.

1. Classical Reduction: Factoring $N$ is shown to be equivalent to finding the period $r$ of the function $f(x) = a^x \pmod N$.
2. Quantum Period Finding:
   • Create a superposition of states.
   • Evaluate $f(x)$ in parallel.
   • Apply the Quantum Fourier Transform (QFT) to extract the period $r$ from the interference pattern.
3. Classical Calculation: Use the period $r$ to calculate the greatest common divisor $\gcd(a^{r/2} \pm 1, N)$ to find the factors.

Cryptographic Implications

Shor's algorithm renders RSA and elliptic-curve cryptography vulnerable once large-scale, fault-tolerant quantum computers are constructed. This has driven the global migration to Post-Quantum Cryptography (PQC).