015 Factoring 15
SimulatorFactor 15 = 3 x 5 by finding the period of a repeating list, like Shor's algorithm. A toy, honest about real scale.
Simulator running in your browser. Real hardware: coming soon (planned provider: IBM Quantum).
What's happening?
Walk through Shor's algorithm on 15: list the powers of a number modulo 15, let a simulated quantum step find the period, and turn it into the factors 3 and 5. A toy, honest about the millions of qubits real attacks would need. Simulator only.
You will learn: Period finding, the idea behind Shor's algorithm.
The idea
Pick a number a that shares no factor with 15, say 7. List 7 to the power x modulo 15 for x = 0, 1, 2, ...: it goes 1, 7, 4, 13, 1, 7, 4, 13 and repeats. The length of the repeat, 4, is the period r. If r is even, then 7 to the power r over 2, which is 4, gives the factors: gcd(4 - 1, 15) = 3 and gcd(4 + 1, 15) = 5. The quantum computer's job is only the period.
How the quantum step finds the period
A counting register of coins is spun into a mix of all values of x, and the list is computed into a second register. Looking at that second register leaves the counting register with only the x values that share one result, evenly spaced by the period. A quantum Fourier transform then makes these evenly spaced values interfere, so the counting register shows peaks at multiples of 16 over r. The bars show 100 readings. This page calculates the Fourier step directly with maths instead of building the full 8 qubit circuit, which the 3 qubit Lab cannot hold.
Honest notes
- It is a toy. Factoring 15 on real hardware was first shown in 2001 on a 7 qubit NMR machine (Vandersypen et al., IBM and Stanford).
- Real attacks are enormous. RSA 2048 or a 256 bit elliptic curve key needs thousands of error corrected logical qubits, and hundreds of thousands to millions of physical ones. See Can a quantum computer break my wallet?, How Many Qubits Do You Need to Break Bitcoin? The Latest Estimates and Shor's Algorithm Explained Step by Step.
- Small demonstrations can mislead. Compiled circuits can seem to factor big numbers with very few qubits, but the difficulty depends on the period, not the size of the number (Smolin, Smith and Vargo, 2013).
- Interference at work again: see the interference maze.
Run on real hardware: coming soon. The planned provider is IBM Quantum. It is not connected yet. Every result on this page comes from a simulator running in your browser, not from a quantum computer.
How it works: the simulator keeps the exact quantum state of the qubits as a list of complex numbers, applies each gate to it, and draws random samples from the resulting probabilities. The random numbers are ordinary pseudo random numbers from your browser, and a real device would add noise. No QNT, wallet or account is needed.
Sources
- Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (arXiv:quant-ph/9508027)
- Vandersypen et al. (2001): Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (arXiv:quant-ph/0112176)
- Smolin, Smith and Vargo (2013): Pretending to factor large numbers on a quantum computer (arXiv:1301.7007)
- Gidney (2025): How to factor 2048 bit RSA integers with less than a million noisy qubits (arXiv:2505.15917)
This is an educational simulator, not financial advice. QUANTUM (QNT) is an independent community token on Solana and does not perform quantum computation.