Factoring by Periods

The idea behind Shor’s algorithm

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Shor’s algorithm reduces factoring N to finding the period of aˣ mod N.
• With even period $r$, $\gcd(a^{r/2} \pm 1, N)$ usually gives the factors.
• Only the period finding needs a quantum computer.

Steps

1. From factors to rhythms
2. Powers of 7
3. Choose a base
4. Extract the factor
5. Where’s the quantum part?
6. Factor 21