Shor's Algorithm

Breaking RSA - period finding and integer factorization on a quantum computer

Breaking Cryptography with Quantum Computers

Shor's algorithm lets a quantum computer factor huge numbers quickly — and the safety of RSA encryption rests on that being hard.

Period Finding: The Heart of Shor's Algorithm

Pick N and a base a, and watch ax mod N repeat. That repeat length, the period r, is what the quantum computer finds; the factors follow from it.

N:a:
Go deeper:Period Finding: The Heart of Shor's Algorithm

Shor's algorithm (1994) showed that a quantum computer could factor large integers in polynomial time — an exponential speedup over the best known classical algorithms. Since RSA encryption relies on the difficulty of factoring, Shor's algorithm threatens the security of nearly all current public-key cryptography.

The key insight: factoring reduces to period finding, which reduces to the Quantum Fourier Transform — a problem quantum computers solve efficiently. This connection between number theory and quantum physics is one of the most beautiful results in computer science.

Given N to factor, pick a random a and compute f(x) = ax mod N. This function is periodic — it repeats with some period r. Finding r is hard classically but easy for a quantum computer using QFT. Once you know r, simple arithmetic gives the factors. Try different values of a and N to see the periodic patterns.

Factoring Step by Step

Choose N and a base a, then click "Next Step →" through the algorithm. Some choices of a fail (odd r or trivial factors); just pick another and retry.

N:a:
Step 1 / 6
Go deeper:Factoring Step by Step

Walk through Shor's algorithm from start to finish. Choose N, pick a random base a, use quantum period-finding to get r, then compute gcd(ar/2±1, N) to extract the factors. Not every choice of a works — if r is odd or gives trivial factors, you try again. On average, only a few attempts are needed.

Why does this work? If ar ≡ 1 (mod N) and r is even, then (ar/2 − 1)(ar/2 + 1) ≡ 0 (mod N). Since neither factor is 0 mod N (usually), gcd with N gives a non-trivial factor.

Breaking RSA Encryption

Pick two primes p and q to build an RSA key, then click "Run Shor's Attack" to factor N and recover the private key.

p:q:msg:
Go deeper:Breaking RSA Encryption

RSA security rests on the assumption that factoring N = p × q is hard when p and q are large primes. The public key (e, N) is published; the private key d requires knowing φ(N) = (p−1)(q−1), which requires the factors. This demo shows how Shor's algorithm recovers the factors and breaks the encryption.

Classical vs Quantum Factoring Scaling

Hover over the rows to compare classical and quantum factoring times as keys grow. For RSA-2048, it is longer than the age of the universe versus minutes.

Classical GNFS (General Number Field Sieve) has sub-exponential complexity ~exp(n1/3). Shor's algorithm has polynomial complexity O(n³). The gap grows dramatically with key size. Hover over table rows for details.

Go deeper:Classical vs Quantum Factoring Scaling

The best classical factoring algorithm (General Number Field Sieve) scales as exp(n1/3) — sub-exponential but still impossibly slow for large keys. Shor's algorithm scales as n³ — polynomial. For RSA-2048 (the current standard), classical factoring would take longer than the age of the universe. Shor's would take minutes on a sufficiently large quantum computer.

Key Takeaways

  • Factoring reduces to finding the period of ax mod N, which the QFT does efficiently.
  • Classical factoring is sub-exponential; Shor's is polynomial, O(n³).
  • A large enough quantum computer would break RSA, ECC and related cryptography.
  • NIST has standardized post-quantum schemes, and the transition is underway.

Spot a mistake or have an idea?

Search