07 · Shor’s move
Period
Shor does not factor by guessing. It finds the period of a modular function, and the QFT reads that period off as peaks. Factoring is the classical wrap.
In English
Shor’s factoring algorithm does not try divisors. It finds how often a modular function repeats (its period). A quantum Fourier transform turns that repeat into peaks you can read. A little schoolbook arithmetic then yields the factors. RSA’s bet is that this period is hard to find.
- Try this
- Feed a repeating pattern. Run the QFT. The peaks are the period. Then read Volume VII if you want the lock this breaks.
- Keep this
- Shor finds a period. Factoring is the wrap. The QFT is the quantum piece.
Lab · a period in, peaks out
Three qubits, eight slots. A periodic list of amplitudes is the cartoon of Shor’s periodic function. The QFT reads the period as peaks in the other basis.
Four kets · QFT two peaks
Time · peaks at |000⟩ |010⟩ |001⟩ |011⟩
|000⟩0.525%|100⟩00%|010⟩0.525%|110⟩00%|001⟩0.525%|101⟩00%|011⟩0.525%|111⟩00%
The quantum Fourier transform is the same idea as a classical DFT: a periodic signal becomes peaks at multiples of the frequency. QFT just does it on amplitudes, reversibly, in quadratic gates.
Factoring N via Shor: pick a coprime a, find the period of aˣ mod N, then a little number theory. RSA’s hardness assumption is “this period is hard.” Continue in Volume VII · RSA.