Section 3.3 Shor’s Algorithm
Subsection 3.3.1 Building Up to the Algorithm
In the field of cryptography, quantum computers could be used to improve the security of our information systems. However, quantum computations can also be used to break through our modern crypto-systems much faster than is possible through classical computing. One method through which quantum computation could be used to break through our modern cybersecurity is with an algorithm created by American mathematician Peter Shor in 1994.
The security behind our modern cryptographic methods lies in the fact that it is very computationally difficult to find the prime factors of large numbers. It takes years of computing time on a classical computer to find the factors of numbers with hundreds of digits. The algorithm designed by Peter Shor takes advantage of quantum concepts to find the prime factors of large numbers much quicker. If a powerful enough quantum computer is ever built it could be used to break most modern encryptions jarringly quickly. Before describing the algorithm, we must first define some terms.
Prime Numbers: A number is prime if the only positive integers that divide it are itself and the number one
Coprime Numbers: Two numbers are coprime (also known as relatively prime or mutually prime) if the only positive integer that is a divisor of both of them is the number one. In other words, two numbers are coprime if their greatest common divisor is one and they share no prime factors
Period of a function: Suppose \(\textbf{x}\) and \(\textbf{y}\) are two binary strings. The period of a function \(f\) would be a binary string \(\textbf{c}\) such that
\begin{equation*}
f(\textbf{x}) = f(\textbf{y}) \text{ if and only if } \textbf{x} = \textbf{y} \oplus \textbf{c}
\end{equation*}
where \(\textbf{x},\textbf{y},\textbf{c} \in \{0,1\}^n\) and \(\oplus\) represents the XOR operation.
A periodic function is any function with a series of outputs that repeat as the inputs continue to increase. The period of a function is the length of the sequence of repeating outputs.
Congruence Relation: The congruence relation comes from the field of modular arithmetic. This relation deals with numbers that have the same remained when divided by a specific value, which is called a modulus.
\begin{equation*}
a \equiv b \text{ mod } m
\end{equation*}
This equation reads "\(a\) is congruent to \(b\) modulo \(m\text{.}\)" Congruence relations have the following properties:
\begin{equation*}
\begin{split} & \text{Reflexive: } a \equiv a \text{ mod } m
\\& \text{Symmetric: } \text{if } a \equiv b \text{ mod } m \text{ then } b \equiv a \text{ mod } m
\\& \text{Reflexive: } \text{if } a \equiv b \text{ mod } m \text{ and } b \equiv c \text{ mod } m \text{ then } a \equiv c \text{ mod } m \end{split}
\end{equation*}
Suppose \(a \equiv b \text{ mod } m \) and \(c \equiv d \text{ mod } m \text{.}\) Congruence relations have the following operations defined:
\begin{equation*}
\begin{split} & \text{Addition: } a + c \equiv b + d \text{ mod } m
\\& \text{Subtraction: } a - c \equiv b - d \text{ mod } m
\\& \text{Multiplication: } ac \equiv bd \text{ mod } m
\\& \text{Exponentiation: } a^n \equiv b^n \text{ mod } m \ \ \ \ \ \ \ \ \text{ }\end{split}
\end{equation*}
An alternate form for the equation \(a \text{ mod } m = r\) is
\begin{equation*}
a = mq + r
\end{equation*}
Here \(r\) is called the remainder and \(q\) is what we want to solve for to find the value of \(a\text{.}\)
For two coprimes \(a\) and \(N\) (where \(aN\)) we propose the sequence
\begin{equation*}
a^0 \text{ mod } N, \ a^1 \text{ mod } N, \ a^2 \text{ mod } N, \ a^3 \text{ mod } N, \ \ldots, \ a^n \text{ mod } N
\end{equation*}
The terms of this sequence are defined by the periodic function \(g_{a,N}\)
\begin{equation*}
g_{a,N}(r) = a^r \text{ mod } N
\end{equation*}
The following examples will show the period of this function for different values of \(a\) and \(N\text{.}\)
Consider \(a=2, \ N=23\text{,}\) and \(r\) running from 0 to \(n\)
\begin{equation*}
\begin{array}{r r r r r r r r r r r r r r r r r}
r&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&\ldots\\
a^r&1&2&4&8&16&32&64&128&256&512&1024&2048&4096&8192&16384&\ldots\\
g_{2, 23}(r)&1&2&4&8&16&9&18&13&3&6&12&1&2&4&8&\ldots
\end{array}
\end{equation*}
Notice that after 11 values of \(r\) the function \(g_{2,23}(r)\) begins to repeat itself. If we continued to write out this sequence as \(r\) continues to increase, we would find that every 11 integers, the sequence repeats again. This means that \(g_{2,23}(r)\) has a period of 11, which means \(g_{2,23}(r) = g_{2,23}(r+11)\text{.}\)
Example 3.3.2. A counterexample.
This example will show what will happen when \(a\) and \(N\) are not coprimes. Consider \(a=2, \ N=24 \text{,}\) and \(r\) running from \(0\) to \(n\text{.}\) \(2\) and \(24\) share the prime factor \(2\) so they are not coprime.
\begin{equation*}
\begin{array}{r r r r r r r r r r r r r r r}
r&0&1&2&3&4&5&6&7&8&9&10&11&12&\ldots\\
a^r&1&2&4&8&16&32&64&128&256&512&1024&2048&4096&\ldots\\
g_{2, 24}(r)&1&2&4&8&16&8&16&8&16&8&16&8&16&\ldots\end{array}
\end{equation*}
As we can see, the function \(g_{2,24}(r)\) does begin to repeat, but it does not repeat the entire sequence. Thus this function is not periodic, which is why we must choose coprimes for \(a\) and \(N\text{.}\)
Example 3.3.3.
Consider \(a=229, / N=247\text{,}\) and \(r\) running from 0 to \(n\)
\begin{equation*}
\begin{array}{r r r r r r r r r}
r&0&1&2&3&4&5&6&\ldots\\
a^r&1&229&52441&12008989&2750058481&629763392149&144215816802121&\ldots\\
g_{229, 247}(r)&1&229&77&96&1&229&77&\ldots\\
\end{array}
\end{equation*}
Notice that after 4 values of \(r\) the function \(g_{229,247}(r)\) begins to repeat itself. If we continued to write out this sequence as \(r\) continues to increase, we would find that every 4 integers, the sequence repeats again. This means that \(g_{229,247}(r)\) has a period of 4, which means \(g_{229,247}(r) = g_{229,247}(r+4)\text{.}\)
Subsection 3.3.2 An Example
Before fully diving into Shor’s algorithm, we will have another example. Suppose we have two prime numbers, \(3, 7.\) We can multiply them togehter to get \((3\times 7 = ) 21\) which a positive number and the result of two prime numbers. Now, think about this
\begin{equation*}
p \times 7 = 21
\end{equation*}
where \(p\) is either prime or the product of primes. We can calculate this number fairly easily. However, if you have
\begin{equation*}
p \times q = 315
\end{equation*}
where \(p\) and \(q\) are either prime or the product of primes. We can still calculate this fairly easily and find that 315 actually has more than two factors
\begin{equation*}
315 = 3 \times 3 \times 5 \times 7 = 3^2 \times 5^1 \times 7^1
\end{equation*}
Instead of trying to solve for \(p\) and \(q\text{,}\) it makes more sense to solve for \(p_1,p_2,\ldots,p_n\) and \(r_1,r_2,\ldots,r_n\) where each \(p_i\) is a prime factor and each \(r_i\) is an exponent that represents how many times \(p_i\) appears as a factor. This means we want to express the number we are looking to factor as
\begin{equation*}
p_1^{r_1} \times p_2^{r_2} \times \ldots \times p_n^{r_n}
\end{equation*}
Subsection 3.3.3 Shor’s Algorithm
Problem 3.3.4. Integer Factorization Problem.
\(\textbf{Input:}\) An integer \(N\)
\(\textbf{Problem:}\) Output positive integers \(p_1,p_2,\ldots,p_n\) and \(r_1,r_2,\ldots,r_n\) where the \(p_i\) are distinct primes and \(N=p_1^{r_1} \times p_2^{r_2} \times \ldots \times p_n^{r_n} \)
The complexity to calculate the prime factors increases rapidly as \(N\) increases.
In 1994, while Peter Shor was working for Bell Labs, his proposed algorithm to quickly factor large numbers sent ripples across the fields of computer science, number theory, quantum computation, and cryptography. While it has not been proven that factoring large numbers can not be achieved on a classical computer in polynomial time, as of 2015 the fastest algorithm publicly available for factoring large number runs in
\begin{equation*}
\mathcal{O}\big(e^{\frac{64}{9}n^{1/3} (\log {n})^{2/3}}\big)
\end{equation*}
operations where \(n\) is the number of bits used to represent the number; this runtime exceeds polynomial time. In contrast Shor’s algorithm runs in
\begin{equation*}
\mathcal{O}((\log{n})^2\log{\log {n}})
\end{equation*}
operations on a quantum computer, and then must perform \(\mathcal{O}(\log{n})\) steps of post processing on a classical computer. Overall this time is polynomial. This discovery propelled the study of quantum computing forward, as such an algorithm has been highly sought after.
- Shor’s algorithm uses quantum parallelism to produce a superposition of all values of this function in one step.
- The Quantum Fourier Transform is used to create a state in which most of the amplitudes are close to multiples of the reciprocals of the functions period.
- With high probability, measuring the state yields information from which, by classical means, the period can be extracted. The period is then used to factor N
The function
\begin{equation*}
f(r) = a^r \text{ mod } N
\end{equation*}
is a periodic function where \(a\) is an integer coprime to \(N\) and \(N\) is the integer we want to factor. Calculating this function for an exponential number of inputs \(r\) would take an exponential amount of time on a classical computer, but an a quantum computer Shor’s algorithm can take advantage of quantum parallelism to perform this exponential number of operations in one step.
The first thing we need to know in order to do Shor’s algorithm is order finding. Let \(a\) and \(N\) be positive integers with no common factors such that \(a < N\text{.}\) The order of \(a\) for the function \(f(r)\) is the smallest positive integer \(r\) such that
\begin{equation*}
f(r) = a^r \text{ mod } N= 1
\end{equation*}
which means
\begin{equation*}
a^r = 1 \text{ mod } N
\end{equation*}
This equation can be expanded
\begin{equation*}
\begin{split} a^r &= 1 \text{ mod } N \\ a^{(r/2)2} &= 1 \text{ mod } N \\ a^{(r/2)2} - 1 &= 0 \text{ mod } N \\ (a^{r/2}+1)(a^{r/2}-1) &= 0 \text{ mod } N \end{split}
\end{equation*}
This tells us that the period of the function \(f\) will be the smallest nonzero value of \(r\) that satisfies the equation \((a^{r/2}+1)(a^{r/2}-1)=0 \text{ mod } N\text{.}\) If \(r\) is even, then \(a^{r/2}+1\) and \(a^{r/2}-1\) are guaranteed to be integers. Since we are looking to find integer factors, if we want to factor \(N\text{,}\) then we must keep choosing values of \(a\) until \(r\) is an even number.
When \(r\) is even, we know that \(N | (a^{r/2}-1)(a^{r/2}+1)\text{.}\) It cannot be the case that \(N | a^{r/2}-1\) because this would imply that \(a^{r/2} = 1 \text{ mod } N\) which cannot be true since \(r\) is the smallest value that satisfies that equation. If we can show that it is also not the case that \(N | a^{r/2}+1\text{,}\) then we will know that \(N\) is a multiple of \((a^{r/2}+1)(a^{r/2}-1)\) but that \(N\) is not a multiple of \(a^{r/2}+1\) nor of \(a^{r/2}-1\text{.}\) This means that \(N\) must share common factors with \(a^{r/2}+1\) and \(a^{r/2}-1\text{.}\)
In order to verify it is not the case that \(N | a^{r/2}+1\) we should first compute
\begin{equation*}
d = \text{GCD}(N,a^{r/2}-1)
\end{equation*}
using the Euclidean Algorithm (we do not describe the Euclidean Algorithm in this webbook, but readers unfamiliar with it may be interested in this link
https://tinyurl.com/4twaxsrf). If we calculate that \(d=1\) then we know that \(N | a^{r/2}+1\text{,}\) which means we will not be able to factor \(N\) using this value of \(a\) and we will need to restart the algorithm with a new value of \(a\text{.}\) If we calculate that \(d\neq 1\) then \(d\) is a factor of \(N\) and \(\frac{N}{d}\) is another factor. If either of these factors are not prime then we can perform the entire algorithm on them again in order to find their factors. We keep repeating this process until we can fully factor \(N\) and represent it as a product of primes.Example 3.3.5.
Suppose we want to find the period of the function \(f\) for \(a=5, \ N=44 \text{.}\) We could use the same method we did in examples 3.2.1, 3.2.2, and 3.3.3
\begin{equation*}
\begin{array}{r r r r r r r r r r r r r}
r&0&1&2&3&4&5&6&7&8&9&10&\ldots\\
a^r&1&5&25&125&625&3,125&15,625&78,125&390,625&1,953,125&9,765,625&\ldots\\
g_{5, 44}(r)&1&5&25&37&9&1&5&25&37&9&1&\ldots\end{array}
\end{equation*}
This method tells us that the period of the function is 5, but it is extremely time consuming. If our values of \(a\) or \(N\) were larger it would be very difficult to perform these operations, even on a powerful computer. This problem can be solved much more efficiently by using a quantum algorithm based on phase estimation .
Subsection 3.3.4 Shor’s Algorithm Restated
- Randomly choose an integer \(a\) such that \(0< a < N\text{.}\) Use the Euclidean algorithm to determine whether \(a\) and \(N\) are relatively prime. If not, we have found a factor of \(N\text{.}\) Otherwise, apply the rest of the algorithm.
- Use quantum parallelism to compute \(f(r)=a^{r} \mod N\) on the superposition of inputs, and apply a quantum Fourier transform to the result.
- Measure the results. With high probability, a value of \(r\) close to a multiple of \(\frac{2^{n}}{r}\) will be obtained.
- Use classical methods to obtain the period \(r\) of \(f(r)\text{.}\)
- Try different values of \(a\) until we calculate an even \(r\text{.}\) Then use the Euclidean algorithm to check efficiently whether \(a^{r / 2}-1\) (or \(a^{r / 2}+1\)) has a nontrivial common factor with \(N\text{.}\)
- Repeat all steps if necessary
