Factoring 15: Shor's Mini-Demo

Factor N=15 using a simplified version of Shor's algorithm.

Factoring 15: Shor's Mini-Demo

Factoring 15 = 3 × 5 is the canonical demonstration of Shor's algorithm on quantum hardware. While 15 has no cryptographic significance, implementing Shor's for this small case illuminates the full algorithm structure: classical preprocessing, quantum period finding, and classical factor extraction.

The Mathematical Framework

To factor N = 15:

1.Pick a random base a where $g cd (a, N) = 1$ . Valid choices: $a \in {2, 4, 7, 8, 11, 13}$
2.Find the period r of $f (x) = a^{x} mod 15$ (the smallest r where $a^{r} \equiv 1 mod 15$ )
3.Attempt factor extraction using $g cd (a^{r /2} \pm 1, 15)$

Let's trace through a = 7:

7^{1} mod 15 = 7

7^{2} mod 15 = 4

7^{3} mod 15 = 13

7^{4} mod 15 = 1 (period r = 4)

Then: $g cd (7^{2} - 1, 15) = g cd (48, 15) = g cd (48 mod 15, 15) = g cd (3, 15) = 3$ ✓ And: $g cd (7^{2} + 1, 15) = g cd (50, 15) = g cd (5, 15) = 5$ ✓

So 15 = 3 × 5 from choosing a = 7 with period r = 4.

What the Quantum Part Does

A quantum computer finds r by:

1.Preparing a superposition of all x values: ∑|x⟩|0⟩ (n input qubits + target qubits)
2.Computing the function: $\sum ∣ x ⟩ ∣ a^{x} mod N ⟩$ (via quantum modular exponentiation)
3.Measuring the target register: this collapses x to a coset of the period
4.Applying QFT to the input register: interference reveals the period r

For N = 15, this requires about 8 qubits total. Experimental demonstrations on IBM quantum hardware achieved this as early as 2001.

Period Values and Success Rate

Not every base a succeeds:

•If r is odd: try a different base (probability ~1/4 for N=15)
•If gcd = 1 or gcd = N: try a different base (probability ~1/4)
•Otherwise: factors extracted with certainty

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 hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Cryptography

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

Previous lessonShor's Algorithm and RSA Next lessonPost-Quantum Cryptography Standards

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