Shor’s Algorithm – Breaking RSA Encryption

In my previous article, I talked about the RSA cryptosystem which is widely used on the Internet for secure data transmission. The power and security of the RSA cryptosystem derives from the fact that the factoring problem is "hard." That is, it is believed that the full decryption of an RSA ciphertext is infeasible because no efficient classical algorithm currently exists for factoring large numbers. However, in 1994 Peter Shor showed that a quantum computer could be used to factor a number n in polynomial time, thus effectively breaking RSA.

It may be tempting to use the speed of a quantum computer to simply check all possible divisors in parallel. In this case, we would be performing a classical algorithm on a quantum computer, making use only of the increased speed of the quantum machine. Unfortunately, this is not going to work. In a way, it is possible for a quantum computer to try all possible divisors. However, due to the nature of quantum computing, when measuring the outcome of the computations, you will get a random possible divisor, which is almost certainly not the one you want.

How, then, can we use a quantum computer to solve the factoring problem? The key to a fast and accurate quantum factoring algorithm is to make use of the structure of the factoring problem itself. Instead of looking for factors directly, we must use some mathematical property of factoring. Fortunately, the factoring problem has plenty of special properties from which to choose. For example, given a positive integer, even if we do not know its prime factorization we do know that it has exactly one factorization. This fact does not help us solve the factorization problem, but it does give us hope that the problem has other nice mathematical properties that will.

The property we will use is the ability to reduce the prime factorization problem into a problem of order (or period) finding. Let’s start by looking at an example. Consider the sequence of numbers

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...

Now, let’s look at this same sequence of powers of two, but taken "mod 15." In other words, we will create a new sequence of numbers consisting of the remainders when each power of two is divided by 15. This gives us the new sequence

2, 4, 8, 1, 2, 4, 8, 1, 2, 4, ...

We see that taking the powers of two mod 15 gives us a periodic sequence whose period (or order) is four. For another example, consider the same powers of two, but taken mod 21. In this case, we have the new sequence

2, 4, 8, 16, 11, 1, 2, 4, 8, 16, ...

Here, we get a periodic sequence whose period is six.

In the 1760s, Euler discovered a beautiful pattern to this period finding problem. Let n be the product of two prime numbers, p and q. Consider the sequence

x \text{ mod } n, x^2 \text{ mod } n, x^3 \text{ mod } n, x^4 \text{ mod } n,…

If x is not divisible by p or q, then the above sequence will repeat with some period that evenly divides (p-1)(q-1).

In our examples above, we have x = 2. In the first example, we have n = 15 which has the prime factors p = 3 and q = 5. Then, (p-1)(q-1) = 8, which is divisible by the period of 4. In the second example, we have n = 21 which has the prime factors p = 3 and q = 7. Then, (p-1)(q-1) = 12, which is divisible by the period of 6.

But how does this help us solve the factorization problem? If we can find the period of the sequence

x \text{ mod } n, x^2 \text{ mod } n, x^3 \text{ mod } n, x^4 \text{ mod } n,…

then we learn something about the prime factors of n. In particular, we learn a divisor of (p-1)(q-1). Of course, we’d rather learn the factors p and q themselves, but this, at least, represents progress. If we determine several random divisors of (p-1)(q-1) by trying different random values of x, then we can multiply those divisors together to obtain (p-1)(q-1) itself. Once we know (p-1)(q-1), we can then determine p and q.

However, there’s still a problem with applying our observations to the factorization problem. Even though the sequence

x \text{ mod } n, x^2 \text{ mod } n, x^3 \text{ mod } n, x^4 \text{ mod } n,…

will eventually start repeating itself, the number of steps before it repeats could be almost as large as n, which in the RSA cryptosystem is a very large number! This issue is why finding the period of the sequence does not appear to lead to a classical factoring algorithm. However, with the help of quantum mechanics, we can define a quantum algorithm that works in a reasonable amount of time.

Shor’s algorithm is composed of two parts. The first part turns the factoring problem into the period finding problem, and can be computed on a classical computer. The second part (step 2 below) finds the period using the quantum Fourier transform and is responsible for the quantum speedup of the algorithm. We begin by briefly describing all five steps. After that, we will focus on the quantum part of the algorithm (i.e. step 2). To factor a large integer n (which, without loss of generality, we may assume is odd), we use Shor’s algorithm:

1. Choose a random positive integer m < n. Compute gcd(m, n), which may be done in polynomial time using the Euclidean algorithm. If gcd(m, n)\neq 1, then we have found a non-trivial factor of n, and we are done. If, on the other hand, gcd(m, n) = 1, proceed to step 2.

2. Use a quantum computer to determine the unknown period P of the sequence

x \text{ mod } n, x^2 \text{ mod } n, x^3 \text{ mod } n, x^4 \text{ mod } n,…

3. If P is an odd integer, then return to step 1. The probability that P is odd is (\frac{1}{2})^k, where k is the number of distinct prime factors of n. If P is even, then proceed to step 4.

4. Since P is even,

(m^{P/2} - 1)(m^{P/2} - 1) = m^{P} - 1 = 0 \text{ mod } n.

If m^{P/2} +1 = 0 \text{ mod } n, then go to step 1. If m^{P/2} +1 \neq 0 \text{ mod } n, then proceed to step 5. It can be shown that the probability that m^{P/2} +1 = 0 \text{ mod } n is less than (\frac{1}{2})^{k-1}, where k denotes the number of distinct prime factors of n.

5. Compute d = gcd(m^{P/2}-1, n) using the Euclidean algorithm. Since m^{P/2} +1 \neq 0 \text{ mod } n, it can be shown that d is a non-trivial factor of n. Exit with the answer d.

Thus, the task of factoring an odd positive integer n reduces to the problem of finding the period of a function/sequence. Shor’s period-finding algorithm (step 2 above) relies heavily on the ability of a quantum computer to be in many states simultaneously (a superposition of states). To compute the period of a function f, we evaluate the function at all points simultaneously.

Unfortunately, quantum mechanics does not allow us to access all of this information directly. Instead, a measurement must be taken which will yield only one of the possible values (destroying all others). Because of this issue, we must transform the superposition to another state that will return the correct period with high probability. This is achieved by using the quantum Fourier transform. The main components of Shor’s period-finding algorithm are as follows:

1. Create a superposition of states. This can be done by applying Hadamard gates to all qubits in the input register.

2. Implement the function f as a quantum transform. To achieve this, Shor used repeated squaring for his modular exponentiation transform.

3. Perform a quantum Fourier transform.

After these transformations, a measurement will yield an approximation to the period P.

Now let’s look at an example of how n = 91 (= 7\cdot 13) can be factored using Shor’s algorithm.

Step 1. Choose a random positive integer m, say m = 3. Since gcd(91,3) = 1, proceed to step 2 to find the period of the function f given by

f(a) = 3^a \text{ mod } 91.

Step 2. Run Shor’s period-finding algorithm on a quantum computer to find (with high probability) that the period P = 6.

Step 3. Since P = 6 is even, we proceed to step 4.

Step 4. Since

3^{P/2} +1 =3^3 + 1 = 28 \neq 0 \text { mod } 91

proceed to step 5.

Step 5. With the Euclidean algorithm, compute

d = gcd(3^{P/2}-1, 91)= gcd(3^{3}-1, 91)= gcd(26, 91) = 13.

We have succeeded in using Shor’s algorithm to find a non-trivial factor of n = 91, namely d = 13.

Sources:

Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-26. doi:http://dx.doi.org/10.1137/S0097539795293172

Lomonaco, Jr, S. J. (2000) Shor’s Quantum Factoring Algorithm. arXiv:quant-ph/0010034