The Trapdoor
For Simon Middlemiss, in memory of that glorious talk we did together in Las Vegas in 2019! Truly one of the very best!
The Rivest-Shamir-Adleman (RSA) cryptosystem publishes a number \(N = pq\) while keeping its prime factors \(p\) and \(q\) secret. Multiplying the primes is routine; no efficient classical algorithm is known for recovering them from a suitably large product.
Shor's algorithm changes that security assumption by reducing factoring to period-finding. The notebook uses \(N = 15\) and \(a = 7\), with one known phase branch compiled into a small circuit. It demonstrates the phase readout and classical post-processing while leaving scalable modular exponentiation outside the circuit.