Shor’s Algorithm

Introduction

Let’s say we want to factor a number $n$.

• Let’s choose a random number $a$, so that $a < n$.
• Now, we want to compute the greatest common divisor between $a$ and $n$.
• If we know it’s not $1$, then it means $a$ and $n$ are not relatively prime, which we know $a$ is one of the divisors of $n$.
• Now, we want to find the period $r$, of the modular function $f(x) := a^x \bmod n$

The period $r$ here is a number, where $a^r \bmod n \equiv 1$, where $r$ is the smallest positive integer.

If $n$ is prime, it’s easy to state that $r = n - 1$ is one of the solution.

It’s easy to say that because $a$ and $n$ is relatively prime, then, $r$ must exist because it’s inversible.

• If we check that the period (which using QFT we can find it fastly), and in classical computer we can find it in $O(n)$:
  • If $r$ is an odd number, or $a^{r/2} = n-1 \bmod n$. Choose a new random number and start over.
  • Successfull iteration, is where $r$ is even, and a classical number theory states that $\text{gcd}(a^{r/2} + 1, n)$ and $\text{gcd}(a^{r/2} + 1, n)$ are both nontrivial factors of $n$.