Shor's Factoring Algorithm

Breaking RSA with quantum mechanics

Shor's algorithm factors integers in polynomial time, an exponential speedup over the best-known classical algorithms. It threatens RSA encryption and demonstrates the profound power of quantum computing.

The Factoring Problem

Given a composite integer N, find its prime factors. The best classical algorithm (the General Number Field Sieve) runs in sub-exponential time. For a 2048-bit RSA key, this would take billions of years on a supercomputer.

Shor's algorithm factors N in O((log N)³) time — polynomial in the number of bits. A sufficiently large quantum computer could break RSA-2048 in hours.

\exp(O((\log N)^{1/3}))

Classical complexity

O((\log N)^3)

Shor's complexity

Period Finding

Shor's algorithm reduces factoring to period finding. Choose a random a < N, and find the period r of the function f(x) = aˣ mod N. Once you have r, you can factor N with high probability using gcd computations.

The quantum part is finding the period using the Quantum Fourier Transform. The classical part (gcd) is efficient on classical computers.

f(x) = a^x \mod N, \quad f(x+r) = f(x)

Period finding

\gcd(a^{r/2} \pm 1, N) \text{ gives factors of } N

Factor from period

Implications

Shor's algorithm is the reason quantum computers are considered a threat to current encryption. All widely used public-key cryptography (RSA, Diffie-Hellman, ECC) can be broken by Shor's algorithm.

Post-quantum cryptography — algorithms resistant to both classical and quantum attacks — is being developed and standardized by NIST to prepare for this future.

•RSA: Shor breaks RSA by factoring the public modulus.
•Elliptic curve: Shor also solves the discrete log problem, breaking ECC.
•Timeline: Fault-tolerant quantum computers needed; estimates range from 5-30 years.
•Post-quantum crypto: NIST is standardizing lattice-based and hash-based alternatives.

Try It Yourself

Run this code in your own environment to experiment with the concepts.

PennyLane: Period Finding Subroutine

The quantum period-finding core of Shor's algorithm.

shor_period.py

import pennylane as qml
from pennylane import numpy as np

n_count = 4
dev = qml.device('default.qubit', wires=n_count+1)

def qft_inverse(wires):
    n = len(wires)
    for i in range(n//2):
        qml.SWAP(wires=[wires[i], wires[n-1-i]])
    for i in range(n):
        for j in range(i):
            qml.ControlledPhaseShift(-np.pi/2**(i-j), wires=[wires[j], wires[i]])
        qml.Hadamard(wires=wires[i])

@qml.qnode(dev)
def period_finding():
    # Counting register in superposition
    for i in range(n_count):
        qml.Hadamard(wires=i)
    # Modular exponentiation (simplified)
    qml.PauliX(wires=n_count)
    # Apply inverse QFT
    qft_inverse(list(range(n_count)))
    return qml.probs(wires=range(n_count))

print('Period finding result:', period_finding())

Self-Check Quiz

1. What is the time complexity of Shor's algorithm for factoring N?

2. What classical problem does Shor reduce factoring to?

3. Which encryption scheme is NOT broken by Shor's algorithm?

Grover's Search Algorithm

Quantum Simulation

import pennylane as qml from pennylane import numpy as np n_count = 4 dev = qml.device('default.qubit', wires=n_count+1) def qft_inverse(wires): n = len(wires) for i in range(n//2): qml.SWAP(wires=[wires[i], wires[n-1-i]]) for i in range(n): for j in range(i): qml.ControlledPhaseShift(-np.pi/2**(i-j), wires=[wires[j], wires[i]]) qml.Hadamard(wires=wires[i]) @qml.qnode(dev) def period_finding(): # Counting register in superposition for i in range(n_count): qml.Hadamard(wires=i) # Modular exponentiation (simplified) qml.PauliX(wires=n_count) # Apply inverse QFT qft_inverse(list(range(n_count))) return qml.probs(wires=range(n_count)) print('Period finding result:', period_finding())