## 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^{227} 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 **sub-exponential** problem (i.e. somewhere between polynomial in **polylogarithmic** (i.e. polynomial in

Since any integer has a unique (up to ordering) prime factorisation^{228} 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** **highest common factor** **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 asR=a^b for some integersa\geqslant 1 andb\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 *apart from*

**Lemma.**
Let

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

Then both

Note that *we assume x to be a non-trivial square root of 1 modulo R*.

*Proof*. The hypothesis tells us that

Now, since

The essence of the above proof is much simpler than the length might suggest: we are sort of just saying that

Or we could appeal directly to the fundamental theorem of arithmetic.
Write ^{229} about prime numbers is that, if *all* the *only*

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

**Lemma.**
Let *and* satisfies

How is this lemma useful to us?
Well, it says that if we randomly pick some *almost*.
The one problem is that

**Lemma.**
Let

R is*not*prime;- the order
r ofy moduloR is even; y^{r/2}>R ;

Then *either* *or* both

*Proof*. First of all, recall that the order *smallest* natural number such that this holds.
So either

The fact that this lemma requires

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 integersa\geqslant 1 andb\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 ofy moduloR 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 to 7 are checking that the necessary hypotheses are satisfied in order for step 8 to calculate factors of ^{230}
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

There are a few algorithms known by this name, but they are all somewhat related.↩︎

This fact so is important that it earns the name of the

**fundamental theorem of arithmetic**↩︎This is the fact that prime numbers are

**prime elements**in the ring of integers. The usual definition of “prime number” that we are used to 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.↩︎