10.11 Shor’s algorithm

Given its importance in the field of (post-)quantum cryptography (and thus in the real world), as well as its fame, it would be remiss of us to not dedicate at least one section in this book to Shor’s algorithm. However, as you will see, the actual quantum part of the algorithm is exactly the order-finding circuit from Section 10.10; the rest is an application of classical number theory to reduce the problem of prime factorisation to the problem of hidden-order determination. Because of this, we will not spend too much time on the details — this is not a book on classical number theory! — but we hope that this section at least highlights the important fact which is that other areas of mathematics and physics have much to offer for the aspiring quantum information scientist. Of course, it is infeasible to try to learn everything in mathematics, but this is also exactly the point: it’s good to be aware that there is a lot of it out there, and that we all have a lot to learn from each others’ specialities.

The purpose of Shor’s algorithm²³² is to find the prime factorisation of a composite integer. This is a classically difficult problem, and hence forms the basis of some very well-known public-key cryptography schemes, such as RSA (see Exercise 10.12.1), but Shor’s algorithm offers a distinct speed-up. More precisely, to factor an integer R classically with the general number field sieve method is a sub-exponential problem (i.e. somewhere between polynomial in R and exponential in R), whereas Shor’s algorithm is polylogarithmic (i.e. polynomial in \log R). This means that Shor’s algorithm witnesses integer factorisation as a bounded-error quantum polynomial time problem: it lives in \texttt{BQP} (recall Section 1.9).

Since any integer has a unique (up to ordering) prime factorisation²³³ consisting of finitely many prime numbers, it suffices to find a single prime factor, since then we can simply divide our original number by this and run the algorithm over and over until it terminates, recording the prime factors that we find along the way. But still, turning the problem of “find a prime factor” into a problem that we have already solved (namely hidden-order determination) requires some work, so let’s get started.

Recall that the greatest common divisor \operatorname{gcd}(m,n) (or highest common factor \operatorname{hcf}(m,n)) of a pair of integers (m,n) is the largest integer that divides both of them. This can be efficiently computed by a (very old) classical algorithm known as Euclid’s algorithm, so we can make use of it in freely. In fact, let us now list the things that we can do efficiently with classical algorithms:

compute the \operatorname{hcf} of two integers (Euclid’s algorithm)
determine if an integer is prime (the Miller–Rabin primality test)
determine if an integer is even (check if the last digit is a 0 in its binary expansion)
determine if an integer R can be written as R=a^b for some integers a\geqslant 1 and b\geqslant 2 (Exercise 10.12.6).

One more small note of terminology: throughout this section, we say factor to mean non-trivial factor, i.e. the factors of R are the natural numbers that divide R apart from 1 and R.

Lemma. Let x and R be natural numbers such that

R is not prime;
1<x<R-1;
x^2\equiv1\ \mathrm{mod}\ R.

Then both \operatorname{hcf}(x-1,R) and \operatorname{hcf}(x+1,R) are factors of R.

Note that 1<x<R-1 is equivalent to saying that x\not\equiv\pm1\ \mathrm{mod}\ R. In other words, we assume x to be a non-trivial square root of 1 modulo R.

Proof. The hypothesis tells us that x^2-1 = kR for some integer k, and so factoring x^2-1 tells us that R \mathbin{\vert}(x+1)(x-1) (where we write a\mathbin{\vert}b to mean that a divides b).

Now, since x<R-1, we know that x+1<R and so R cannot divide x+1 because it is simply too big. This means, in particular, that \operatorname{hcf}(x+1,R)\neq R. But now note that if \operatorname{hcf}(x-1,R)=1 then, since R\mathbin{\vert}(x+1)(x-1), it must be the case that R\mathbin{\vert}x+1, and we have just said that this cannot happen. The same argument applies if we swap x+1 and x-1, so we have proven that both \operatorname{hcf}(x-1,R) and \operatorname{hcf}(x+1,R) are factors of R.

The essence of the above proof is much simpler than the length might suggest: we are sort of just saying that R cannot divide either x+1 or x-1 alone, and so must be “split up” into two parts, with one inside x+1 and the other inside x-1.

Or we could appeal directly to the fundamental theorem of arithmetic. Write R=p_1^{a_1}\ldots p_n^{a_n}, and now consider each prime factor individually. Since R\mathbin{\vert}(x+1)(x-1), we know that p_1\mathbin{\vert}(x+1)(x-1). A very useful fact²³⁴ about prime numbers is that, if p divides a product ab, then either p divides a or p divides b. So here we see that p_1 must divide either x+1 or x-1. We can continue like this for all the prime factors p_i of R, but note that it cannot be the case that all the p_i divide only x+1 and not x-1, since this would then force p_1^{a_1}\ldots p_n^{a_n}=R to divide x+1, which we have already said cannot happen (and similarly for all the p_i dividing only x-1). This means that both \operatorname{hcf}(x-1,R) and \operatorname{hcf}(x+1,R) are non-trivial.

Now let’s state another useful lemma (which we will not prove).

Lemma. Let R be an odd natural number with m\geqslant 2 distinct prime factors. If y is chosen uniformly at random from the set of natural numbers that are coprime to and smaller than R, then the probability that the order r of y modulo R is even and satisfies y^{r/2}\not\equiv-1\ \mathrm{mod}\ R is at least 1-\frac{1}{2^m-1}.

How is this lemma useful to us? Well, it says that if we randomly pick some 1<y<R satisfying the hypotheses, then with non-zero probability (that increases as R has more and more prime factors) it will be such that we can apply the previous lemma to x=y^{r/2}, almost. The one problem is that x>y, and so it might also be the case that x>R, and the previous lemma needed the assumption that x<R-1. But we can fix this!

Lemma. Let y and R be natural numbers such that

R is not prime;
the order r of y modulo R is even;
y^{r/2}<R;

Then either y^{r/2}+1 is divisible by R, or both \operatorname{hcf}(y^{r/2}-1,R) and \operatorname{hcf}(y^{r/2}+1,R) are factors of R.

Proof. First of all, recall that the order r is the smallest natural number such that y^r\equiv1\ \mathrm{mod}\ R. Since r is even, y^{r/2} is well defined and we can factor kR=y^r-1=(y^{r/2}+1)(y^{r/2}-1) as before. Now we have to do something different, because it is no longer necessarily the case that y^{r/2}+1 is smaller than R. However, we can still show that R does not divide the y^{r/2}-1 term, since if it did then we would have that y^{r/2}\equiv1\ \mathrm{mod}\ R which contradicts the fact that r is the smallest natural number such that this holds. So either R divides the y^{r/2}+1 term, or it doesn’t; in the latter case, we can then apply exactly the same argument as before to show that both \operatorname{hcf}(y^{r/2}-1,R) and \operatorname{hcf}(y^{r/2}+1,R) are factors of R.

The fact that this lemma requires R to be odd and also have at least two distinct prime factors means that we can only apply it if we have checked that both of these things are true. In other words, we need to know that R is not even, and also that R is not of the form p^b for some prime p. But as we’ve already mentioned, both of these properties can be checked by an efficient algorithm by a classical computer.

Now we’re ready to state Shor’s algorithm.

Shor’s algorithm. (Factoring the natural number R.)

Check that R is not prime.

If so, stop and return the factor R.
Check if R is even.

If so, stop and return the factor 2.
Check if R=a^b for some integers a\geqslant 1 and b\geqslant 2.

If so, stop and return the factor a.
Uniformly at random pick an integer 1<y<R and evaluate \operatorname{hcf}(y,R); check if \operatorname{hcf}(y,R)>1.

If so, stop and return the factor \operatorname{hcf}(y,R).
Compute the order r of y modulo R via hidden-order determination (from Section 10.10).
Check if r is odd.

If so, go back to step 4.
Check if y^{r/2}\equiv-1\ \mathrm{mod}\ R.

If so, go back to step 4.
Compute \operatorname{hcf}(y^{r/2}-1,R) and \operatorname{hcf}(y^{r/2}+1,R).

Stop and return these as factors.

Picking it apart, we see that steps 1 to 3 are simply checking easy cases; steps 4, 6, and 7 are checking that the necessary hypotheses are satisfied in order for step 8 to calculate factors of R. The only place that we use anything quantum in in step 5, where we have to do hidden-order determination.²³⁵ The fact that steps 6 and 7 won’t cause us to get stuck in an endless loop is justified by the fact that they will both be passed over with probability 1-1/(2^{m-1}), as we mentioned above.

There are a few algorithms known by the name of “Shor’s algorithm”, but they are all somewhat related.↩︎
The fact that prime factorisation is essentially unique is so is important that it earns the name of the fundamental theorem of arithmetic.↩︎
This “very useful fact” is secretly just the fact that prime numbers are prime elements in the ring of integers. The usual definition of “prime number” that we are used to (“only divisible by 1 and itself”) actually says that they are irreducible elements. The link between these two concepts requires some knowledge of ring theory.↩︎
Even better, thanks to a result by Ekerå, one can be rather sure that this quantum subroutine will only need to be run a single time.↩︎