QCFundamentals home

Shor's Algorithm for Factoring

Shor's algorithm factors a composite integer into primes. It reduces factoring NN to order finding: choose an integer aa that is co-prime to NN and find the smallest positive integer rr such that ar≡1 (mod N)a^r \equiv 1\ (\text{mod}\ N). A quantum computer finds that order with the quantum Fourier transform. When rr is even, and ar/2≢−1 (mod N)a^{r/2} \not\equiv -1\ (\text{mod}\ N), the greatest common divisors of NN with ar/2−1a^{r/2} - 1 and with ar/2+1a^{r/2} + 1 are non-trivial factors. This lesson derives that classical step. The quantum subroutine is the order-finding lesson.

What you will learn

  • State what Shor's algorithm factors, and which step is quantum.
  • Turn an even order into two factors with the greatest common divisor.
  • See why an odd order, or a trivial divisor, means trying another base.
  • Factor 1515 from the order of 77 modulo 1515.

Prerequisites

Read order finding first. That lesson uses the quantum Fourier transform and continued fractions to recover rr. Both sit in the quantum algorithms chapter.

How Shor's algorithm works

Let NN be composite. The procedure is:

  1. Pick a random integer aa with 1<a<N1 < a < N. If gcd⁡(a,N)\gcd(a, N) is not 11, that divisor is already a factor of NN.
  2. Otherwise aa and NN are co-prime, so an order rr exists. Quantum order finding returns the smallest such rr.
  3. If rr is odd, try another aa. If r=2mr = 2m is even and am≢−1 (mod N)a^m \not\equiv -1\ (\text{mod}\ N), then gcd⁡(N,am−1)\gcd(N, a^m - 1) and gcd⁡(N,am+1)\gcd(N, a^m + 1) are non-trivial factors of NN.

Shor's algorithm was first proposed by Peter Shor in 1994. In "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" he presented the quantum algorithm for order finding, then showed that the order gives a factorisation.

Why factoring matters

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 NN such that N=p×qN = p \times q where pp and qq are large prime numbers. NN forms the "public" key that is exposed to everyone and pp and qq form the private key 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 NN would give an attacker the ability to read any encrypted message sent to the owner of the private keys.

From the order to the factors

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

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

Since aa and NN are co-prime we know that there must exist some rr such that:

ar≡1 (mod N)a^r \equiv 1\ (\text{mod}\ N)

This is our order-finding problem. We use the quantum order-finding algorithm to find rr.

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

a2m≡1 (mod N)(am)2≡1 (mod N)(am)2−1≡0 (mod N)(am+1)(am−1)≡0 (mod N)a^{2m} \equiv 1\ (\text{mod}\ N) \\[3ex] (a^m)^2 \equiv 1\ (\text{mod}\ N) \\[3ex] (a^m)^2 - 1 \equiv 0\ (\text{mod}\ N) \\[3ex] (a^m + 1)(a^m - 1) \equiv 0\ (\text{mod}\ N)

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

(am+1)(am−1)N=k\frac{(a^m + 1)(a^m - 1)}{N} = k

where kk is an integer.

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

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

Taking a look at the other term, it is actually always the case that gcd⁡(N,am−1)≠N\gcd(N, a^m - 1) \neq N. This is because if am−1a^m - 1 was a multiple of NN then we would have am≡1 (mod N)a^m \equiv 1\ (\text{mod}\ N) which would mean that, sincem=r/2m = r/2 and thus m<rm < r, we would have found a smaller order of aa and NN. Our order-finding algorithm 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 am+1a^m + 1 or am−1a^m - 1 are a multiple of NN. But since their product is divisible by NN it must be the case that one of them is a multiple of pp and the other a multiple of qq.

This means calculating gcd⁡(N,am+1)\gcd(N, a^m + 1) and gcd⁡(N,am−1)\gcd(N, a^m - 1) will now give us our factors pp and qq.

Exercise: factor 15

Apply the above algorithm to factor the number 1515.

Show solution

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 NN 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⁡\gcd operations will always yield two non-trivial (not 11 or NN) factors.

Related lessons