Shor's Algorithm

We're here! We've made it. Finally after all the build-up, we're finally ready to see how quantum computers can factor large numbers into prime factors!

And quite surprisingly, this may be one of the shortest articles. We won't even use any quantum computing here!

Being able to factor large numbers is hugely important since it forms the backbone of all modern encryption. Specifically, RSA encryption uses a system where we define some number $N$ such that $N = p \times q$ where $p$ and $q$ are large prime numbers. $N$ forms the "public" key that is exposed to everyone and $p$ and $q$ form the "private" that should be kept secret.

So we can see that having some machine that could factor composite numbers quickly would allow us to easily obtain the private key from the public key.

We won't go into the specifics of RSA encryption here, but just know that factoring $N$ would give an attacker the ability to read any encrypted message sent to the owner of the private keys.

Shor's algorithm was first proposed by Peter Shor in 1994. In fact, we've already seen half of it. In his original paper: "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" he first presented the fast quantum algorithm for solving the order-finding problem and then showed that that algorithm gives us a way to do factorisation.

Let's see how we can use order-finding to factor $N$!

We start by choosing some random value $a$ such that $1 < a < N$. We then calculate the greatest common divisor of $a$ and $N$. If the greatest common divisor is not 1, then we have found a factor of $N$ (either $p$ or $q$) already, so we can stop here. If the greatest common divisor is 1, then we move on to the next step.

Since $a$ and $N$ are co-prime we know that there must exist some $r$ such that:

This is our order-finding problem. We simply use our fast quantum algorithm from the previous article to find $r$.

If $r$ turns out to be odd, we're out of luck and we must try another value of $a$. Once we've got an even value of $r$ we know that $r=2m$ for some $m$ so we have:

This looks really promising as we have two integers on the left hand side which multiply to a value that is congruent to $0$ mod $N$. This is another way of saying that $N$ divides $(a^m + 1)(a^m - 1)$. More specifically:

where $k$ is an integer.

This must mean that $p$ and $q$ appear somewhere in the prime factorisation of the numerator since $N = p \times q$.

We will use an already existing fast classical algorithm to compute the greatest common divisor (we will use the term $\gcd$ from now on) of $N$ and $a^m + 1$. If $\gcd(N, a^m + 1) = N$ (in other words, $a^m + 1$ is a multiple of $N$) then it unfortunately means we have both $p$ and $q$ in the factorisation of $a^m + 1$ so we can't extract any factors and we have to start our algorithm again from the begining.

Taking a look at the other term, it is actually always the case that $\gcd(N, a^m - 1) \neq N$. This is because if $a^m - 1$ was a multiple of $N$ then we would have $a^m \equiv 1\ (\text{mod}\ N)$ which would mean that, since$m = r/2$ and thus $m < r$, we would have found a smaller order of $a$ and $N$. Our order-finding algorthim is always guaranteed to give us the smallest possible order so this would be a contradiction.

Ok, so we're now at a point where neither $a^m + 1$ or $a^m - 1$ are a multiple of $N$. But since their product is divisible by $N$ it must be the case that one of them is a multiple of $p$ and the other a multiple of $q$.

This means calculating $\gcd(N, a^m + 1)$ and $\gcd(N, a^m - 1)$ will now give us our factors $p$ and $q$.

Exercise

This is amazing! Our fast order-finding quantum algorithm has given us a tool to factor large numbers into their prime factors without needing any extra quantum algorithm!

Now if $N$ had more than two prime factors we might require some more work to find the other factors, but the process remains more-or-less the same. The final two $\gcd$ operations will always yield two non-trivial (not $1$ or $N$) factors.