Shor's algorithm and RSA

The security of most of the internet rests on one bet: that multiplying two large primes is easy but recovering them from the product is not. Shor's algorithm collects on the opposite side of that bet. And the surprise is how little of it is quantum - almost the entire algorithm is grade-school number theory, with one exponentially hard step handed off to the quantum Fourier transform you just met. That single handoff is enough to break RSA.

Factor a number by hand, watching the period

The reduction is easier to trust once you have run it. Pick a modulus $N$ and a base $a$ below. The widget plots $a^x\mathrm{mod}N$, which always eventually repeats, shades one full period $r$, and then finishes the job with two greatest-common-divisor computations. Try $N=15,a=2$, then hunt for a base where it fails and makes you retry.

Everything on screen except finding the period is cheap classical arithmetic. The plot repeats; the two gcds are instant. The one step that does not scale - locating the period when $N$ is hundreds of digits long - is the step the quantum computer takes over.

The reduction, step by step

To factor $N$, pick a random $a$ with $1<a<N$. If $\gcd (a,N)>1$ you already stumbled onto a factor and you are done. Otherwise, look at the sequence $a^0,a^1,a^2,\dots (\mathrm{mod}N)$. Because there are only finitely many residues, it must cycle, and its period $r$ is the smallest positive exponent with

Now the algebra that turns a period into factors. If $r$ is even, write $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$. Since $a^r-1\equiv 0(\mathrm{mod}N)$, the product of those two factors is a multiple of $N$, so - as long as $a^{r/2}\not\equiv -1(\mathrm{mod}N)$ - each shares a real factor with $N$:

That is the whole classical wrapper, and it is what the widget computed. Roughly half of random bases give an even $r$ that avoids the $-1$ trap, so a couple of tries almost always works. The catch is the missing piece: for a real RSA modulus, computing the period $r$ by classical means is itself as hard as factoring. No speedup there.

Why RSA falls

RSA publishes a modulus $N=pq$ and trusts that nobody can recover the primes $p$ and $q$. The best classical factoring algorithms run in time that grows nearly exponentially in the number of digits, so a 2048-bit modulus is safe against every classical machine for the foreseeable future. Shor factors in time polynomial in the number of digits. A large enough, reliable quantum computer therefore recovers $p$ and $q$ from the public $N$, and the whole scheme unravels. The same period-finding idea also breaks Diffie-Hellman and elliptic-curve cryptography, which rest on a close cousin, the discrete logarithm.

from math import gcd
from random import randrange

def shor(N):
    a = randrange(2, N)
    g = gcd(a, N)
    if g > 1:
        return g, N // g          # lucky: a shared a factor with N

    r = quantum_find_period(a, N) # the ONLY quantum step (QFT-based)

    if r % 2 != 0 or pow(a, r // 2, N) == N - 1:
        return shor(N)            # bad base, retry with a fresh a

    return gcd(pow(a, r // 2) - 1, N), gcd(pow(a, r // 2) + 1, N)

Check yourself

The consequence for real systems - what to migrate, what survives, and how soon - is the subject of the state-of-the-field and post-quantum cryptography lesson.^[2]