shor's factoring algorithm

We want to find a non-trivial factor of \(N\).

The strategy: we will find \(y \not\equiv \pm 1 \pmod{N}\) such that \(y^2 \equiv 1\). Then, \(y^2 - 1 \equiv 1 \pmod{N}\). So \((y+1)(y-1) \equiv 1 \pmod{N}\). Then, \((y+1)(y-1) = mN\) for some \(m\). Then, one of \((y+1)\) or \((y-1)\) is a factor of \(N\). It can be recovered by taking, e.g., \(\gcd(y-1, N)\).

If \(x\) has an even order \(\pmod{N}\), then, \(x^r \equiv \pmod{N}\) and we can take \(y=x^{r/2}\).

We can use the order finding algorithm to find \(r\). If we select an \(x\) at random, it turns out that it will have an even order and \(x^{r/2} \not\equiv \pm 1\) with high probability.