Shor's Algorithm — High-Level
Reduce factoring to period-finding, then use a quantum subroutine.
Rendering…
Make it your own.
flowchart LR
N[Input integer N] --> Pick[Pick random a < N]
Pick --> GCD{"gcd(a,N) > 1?"}
GCD -- yes --> Done["Factor found:<br/>gcd(a,N)"]
GCD -- no --> Q["Quantum period finding<br/>for f(x) = a^x mod N"]
Q --> P[Period r]
P --> Check{"r even and a^{r/2} ≢ ±1?"}
Check -- no --> Pick
Check -- yes --> Compute["Compute gcd(a^{r/2} ± 1, N)"]
Compute --> Factor[Non-trivial factors of N]