Shor's Algorithm and RSA

Understand why Shor's algorithm breaks RSA and what key sizes are safe.

Shor's Algorithm and RSA

RSA is the most widely used public-key cryptosystem in the world, securing web traffic (TLS), email (PGP), and software signatures. Its security rests on a single computational assumption: factoring large integers is hard. Peter Shor's 1994 algorithm shows that a sufficiently powerful quantum computer can factor integers in polynomial time, threatening the entire RSA infrastructure.

Why Factoring Matters for RSA

RSA key generation:

1.Choose two large primes p and q (each ~1024-2048 bits)
2.Compute N = p × q (the public modulus)
3.Choose public exponent e (usually 65537)
4.Compute private exponent d such that e × d ≡ 1 (mod φ(N)) where φ(N) = (p-1)(q-1)

The public key is $(N, e)$ . The private key is $d$ . Encryption: $C = M^{e} mod N$ . Decryption: $M = C^{d} mod N$ .

Security relies on: given N, it is computationally infeasible to compute φ(N) without knowing p and q. But if you can factor N into p × q, computing φ(N) = (p-1)(q-1) is trivial, and the private key d follows immediately.

Shor's Algorithm: The Structure

Shor's algorithm has two parts:

Quantum part: Period finding. Given N to factor and a random base a with gcd(a, N) = 1, the quantum computer finds the period r of the function:

f (x) = a^{x} mod N

The period r is the smallest positive integer where $f (x + r) = f (x)$ , i.e., $a^{r} \equiv 1 (mod N)$ . A quantum Fourier transform (QFT) finds this period exponentially faster than any classical algorithm.

Classical part: Factor extraction. If r is even and $a^{r /2} \neq \equiv - 1 (mod N)$ , then:

g cd (a^{r /2} - 1, N) and g cd (a^{r /2} + 1, N)

give non-trivial factors of N with high probability. If these conditions aren't met, try a different base a.

Complexity Comparison

Method	Complexity	Example: RSA-2048
Trial division	$O (N)$	$\sim 1 0^{307}$ operations
Number field sieve (best classical)	$L_{N} [1/3, (64/9)^{1/3}] = exp ((64/9)^{1/3} (ln N)^{1/3} (ln ln N)^{2/3})$	$\sim 1 0^{34}$ operations
Shor's algorithm	$O ((lo g N)^{3})$	$\sim 1 0^{9}$ operations

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A guided reading lesson with interactive knowledge checks. Concepts are explained step by step with circuit diagrams and runnable examples, and you confirm understanding before moving on.

Part of: Quantum Cryptography

Master quantum key distribution, the threat quantum computers pose to classical cryptography, and post-quantum cryptographic standards.

Previous lessonGrover's Attack on Symmetric Cryptography Next lessonFactoring 15: Shor's Mini-Demo

This lesson is part of Pro

Unlock Quantum Cryptography and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground