The cryptography of computers: hashes, AES and HMAC, RSA and its weak keys, Diffie–Hellman, Shor and Grover on a quantum computer, ML-KEM, BB84, Shamir’s shares, time locks, passwords.
Quantum Computer
A register of up to 20 qubits simulated as its state vector, with Hadamard, controlled-phase and swap gates, the quantum Fourier transform and seeded measurement. Shor’s algorithm runs as his 1994 paper sets it out — superposition, modular exponentiation, the transform, continued fractions — and Grover’s search as his 1996 paper does, the marked amplitude checked against sin((2k + 1)θ). A simulation: no noise, no error correction.
About this tool
History
In 1994 Peter Shor showed that a quantum computer could factor a number in polynomial time, by finding the period of a^x mod N with a quantum Fourier transform — the result that made RSA mortal and set off the search for post-quantum cryptography. In 1996 Lov Grover showed that an unsorted list of N items could be searched in about √N steps, which halves the strength of every symmetric key in bits. In 2001 Vandersypen and colleagues ran Shor’s algorithm on seven nuclear-magnetic-resonance qubits and factored 15.
How it works
The register is held as its state vector, 2^n complex amplitudes, and the gates act on it exactly: Hadamards, controlled phases, swaps, the quantum Fourier transform built from them, and measurement from a seeded source. Shor’s run builds the state |x⟩|a^x mod N⟩ over every x, measures the work register, transforms the x register and shows the probabilities it leaves, piled on multiples of 2^t / r; a measurement y is read by continued fractions into the period r, and the factors come from gcd(a^(r/2) ± 1, N). Grover’s run applies the oracle and the diffusion k times and records the marked item’s amplitude after each.
How it was checked
The tests confirm that a Hadamard twice is the identity and the transform of |0⟩ is uniform; that 15 with a = 7 gives the period 4 and the factors 3 and 5, the probability exactly a quarter on each of 0, 64, 128 and 192, and with a = 11 the period 2; that for 21 more than Shor’s 4/π² of the probability lies within one of the peaks and 16 of 24 seeded runs factor it; that 35 and 91 factor; and that Grover’s marked amplitude equals sin((2k + 1)θ) at every step, certain after one iteration among four, 99.9 % at the best k among 1024, and lower again past it.
Limits
A simulation: at most 20 qubits, since every amplitude is held in memory, so N at most 127 for Shor, and above 87 the x register is smaller than the 2^t ≥ N² his analysis asks for. No noise, no error correction; Grover’s oracle is given the marked item, as the algorithm assumes. Where a convergent gives a divisor of the period, its small multiples are tried, as Shor allows; a run that fails is repeated with a new seed, as his algorithm repeats.
- Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26 (1997), 1484–1509; arXiv quant-ph/9508027
- Lov K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of the 28th STOC (1996), 212–219; arXiv quant-ph/9605043
- L. M. K. Vandersypen et al., “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”, Nature 414 (2001), 883–887: 15 factored on seven qubits