Notebook 14 — Shor breaks RSA

The moment the book has been building toward. We run Shor’s algorithm on N=15, 21, 35, see it succeed, fail, retry, and finally factor.

import numpy as np
from pqc_edu.quantum.shor import factor

One quick success: N=15

Seed chosen so the first few attempts succeed.

rng = np.random.default_rng(0)
result = factor(15, rng, max_attempts=10)
print('factors:', result.factors)
print('quantum runs:', result.total_quantum_runs)
print('attempts:')
for i, att in enumerate(result.attempts):
    print(f'  {i+1}. a={att.a}, measured={att.measured}, r={att.inferred_period}, status={att.status}')

factors: (3, 5)
quantum runs: 1
attempts:
  1. a=13, measured=64, r=4, status=success

Note: simulation shortcut

We implement the \(a^x \bmod N\) step as a state-vector update over all basis states at once, rather than building a polynomial-size reversible arithmetic circuit. The algorithmic behavior (creating the superposition \(\sum_x |x\rangle|a^x \bmod N\rangle\)) is identical; only the classical work done by our simulator is exponential. This is a simulation shortcut, not an algorithmic one — a real quantum computer would use modular-exponentiation gates that scale polynomially in \(n\).

N=21 and N=35

Larger circuits; more counting qubits help resolve the period.

for N in (21, 35):
    rng = np.random.default_rng(1 + N)
    result = factor(N, rng, max_attempts=20)
    print(f'\nN={N}: factors = {result.factors}  (after {result.total_quantum_runs} quantum runs, {len(result.attempts)} total attempts)')
    for i, att in enumerate(result.attempts):
        print(f'  {i+1}. a={att.a}, measured={att.measured}, r={att.inferred_period}, status={att.status}')

N=21: factors = (7, 3)  (after 2 quantum runs, 3 total attempts)
  1. a=16, measured=0, r=None, status=period_not_found
  2. a=8, measured=0, r=None, status=period_not_found
  3. a=7, measured=-1, r=None, status=a_not_coprime

N=35: factors = (7, 5)  (after 0 quantum runs, 1 total attempts)
  1. a=14, measured=-1, r=None, status=a_not_coprime

Success rate over many seeds

Shor is probabilistic — each run picks a random \(a\). Some choices fail (odd period, trivial square root, …). We run it 100 times with different seeds and count how often a single attempt suffices.

first_try_success = 0
success_eventually = 0
total = 100
for seed in range(total):
    rng = np.random.default_rng(seed)
    result = factor(15, rng, max_attempts=10)
    if result.factors is not None:
        success_eventually += 1
        if len(result.attempts) == 1:
            first_try_success += 1
print(f'N=15 success rate (first try):   {first_try_success}/{total}')
print(f'N=15 success rate (within 10):  {success_eventually}/{total}')

N=15 success rate (first try):   66/100
N=15 success rate (within 10):  100/100

Status breakdown

What happens when it fails?

from collections import Counter
all_statuses = Counter()
for seed in range(total):
    rng = np.random.default_rng(seed)
    result = factor(15, rng, max_attempts=10)
    for att in result.attempts:
        all_statuses[att.status] += 1
print('attempt outcomes across 100 seeds of N=15:')
for s, c in sorted(all_statuses.items(), key=lambda kv: -kv[1]):
    print(f'  {s:22s} {c}')

attempt outcomes across 100 seeds of N=15:
  a_not_coprime          67
  period_not_found       37
  success                33
  trivial_factor         13

RSA scaling note

ML-KEM-512 replaces RSA-2048 and above. RSA-2048 requires ~4096 qubits for Shor. Our simulator maxes out around 14 qubits (N ≤ 35). The gap between “factor 35 in a simulator” and “factor \(2^{2048}\)” is about 10 orders of magnitude in problem size. This is why Q-Day is still a debate: building a 4000-qubit fault-tolerant quantum computer is vastly harder than anything built today.

→ Final chapter: 15_shor_vs_lattice.ipynb — why this trick does not break ML-KEM.