Period finding for N = 15, 21, 35: exact QFT peak histogram, sampled shots, continued fractions and the resulting factors.
Check running...
The science
To factor N, pick a base a coprime to N and find the order r: the smallest r with ar ≡ 1 (mod N). If r is even and ar/2 ¬≡ −1 (mod N), then gcd(ar/2 ± 1, N) are non-trivial factors.
The quantum part prepares (1/√Q)Σx|x⟩|ax mod N⟩ with Q = 2t ≥ N². Measuring the second register picks a value y and leaves the first register uniform over x = x0 + kr (K terms). The inverse QFT gives
P(c) = |Σk=0..K−1 e2πi k r c/Q|² / (QK), with peaks at c ≈ jQ/r. This page computes P(c) exactly by direct summation (no FFT shortcut, no sampling approximation) and draws shots from it.
Classically, from a shot c the continued fraction of c/Q gives convergents n/d; a denominator d < N that makes ad ≡ 1 (trying small multiples of d) is accepted as the period. When Q ≥ N² and |c/Q − j/r| ≤ 1/(2Q), the convergent is the reduced fraction j/r, so its denominator divides r.
Check: the true order is found by brute force (repeated multiplication). For every on-peak shot we require d | r, and every on-peak shot must return exactly the brute-force order (an off-peak shot can still return a multiple of r, which is reported separately, never a non-multiple). A separate self-test runs 40 shots for every base of N = 15, 21, 35.
Simplifications: this is a classical simulation of the quantum state (it needs memory growing with Q), not a speed-up; ideal noiseless qubits; the modular-exponentiation circuit is replaced by its truth table. Off-peak shots (a few per cent to tens of per cent) are real features of the algorithm and are reported separately. Only tiny N are practical here; factoring 15 on real hardware has used much-reduced circuits.