Shor’s Algorithm: How Quantum Computers Could Break RSA

01 RSA’s one-way door

RSA chooses two large primes p and q, publishes their product N = pq, and relies on the difficulty of recovering p and q from N. Encryption and signatures use modular exponentiation; the private key depends on the factorization. Multiplication is easy to verify, while reversing it for a cryptographically sized modulus is believed to be infeasible for classical computers.

That asymmetry is a design feature, not a law of nature. Shor’s algorithm changes the computational question: instead of searching directly for factors, it finds the period of a modular function using quantum interference.

02 The period hiding inside factoring

Pick a number a coprime to N and study f(x) = aˣ mod N. Modular arithmetic cycles, so there is a smallest positive period r with aʳ ≡ 1 (mod N). If r is even and aʳ⁄² is not congruent to −1, the greatest common divisors gcd(aʳ⁄² − 1,N) and gcd(aʳ⁄² + 1,N) reveal non-trivial factors.

For a toy example, take N = 15 and a = 2. The sequence 2, 4, 8, 1 repeats with period r = 4; 2² = 4, so gcd(4−1,15)=3 and gcd(4+1,15)=5. The hard part is finding r efficiently for a huge N.

03 What the quantum computer actually does

Shor’s order-finding subroutine prepares a superposition of candidate x values, computes modular exponentiation coherently, and applies the quantum Fourier transform (QFT). Amplitudes from inputs separated by the period interfere constructively at frequency peaks. A classical continued-fraction algorithm then turns the measured phase estimate into a candidate period.

The QFT is not “try every key and read the answer.” Measurement returns one sample. The speedup comes from the structured interference distribution and from repeating the experiment enough times to obtain a useful denominator.

04 From period to factors

Once a candidate even r is obtained, the final classical step is short. If the candidate fails—because r is odd, or because aʳ⁄² ≡ −1 mod N—the algorithm chooses a new a and repeats. This hybrid structure is typical of quantum algorithms: a quantum circuit creates a distribution that a classical computer post-processes.

from math import gcd N, a, r = 15, 2, 4
x = pow(a, r // 2, N)
p = gcd(x - 1, N)
q = gcd(x + 1, N)
print(f"period={r}, factors=({p}, {q})")

05 Why RSA is not broken today

Running Shor’s algorithm at cryptographically relevant scale requires a fault-tolerant quantum computer, not a noisy demonstration that factors 15 or 21. Logical qubits must survive deep modular-exponentiation circuits, and error correction adds substantial physical-qubit and time overhead. Resource estimates vary with architecture and error rates; they are engineering forecasts, not current capabilities.

The risk is practical because encrypted traffic can be recorded now and decrypted later—a “harvest now, decrypt later” problem. Migration to post-quantum cryptography begins before a cryptographically relevant quantum computer exists.

06 The post-quantum response

Post-quantum cryptography replaces factoring- and discrete-log-based assumptions with problems believed to resist both classical and quantum attacks. NIST’s standardized families include lattice-based key establishment and signatures, plus hash-based signatures. The transition touches certificates, firmware, VPNs, backups, long-lived secrets, and every system that authenticates software or machines.

RSA remains useful today when correctly implemented and sized, but cryptographic agility matters. Inventory what is protected, identify data with a long confidentiality lifetime, and plan hybrid or post-quantum deployments rather than waiting for a headline called “Q-day.”

07 A complexity comparison

Classically, the best known general-purpose factoring methods are sub-exponential: faster than brute force but slower than a polynomial. Shor’s algorithm is polynomial in the number of bits, using quantum order finding plus classical arithmetic. “Polynomial” does not mean cheap at today’s hardware scale; it means the asymptotic shape changes dramatically as the modulus grows.

The minutephysics video makes the danger intuitive by connecting RSA to a period-finding trick. The sober conclusion is equally important: the cryptographic deadline is set by migration lead times, not by the date a machine finally factors a live RSA key.