Note: Thanks to minutephysics for the primer that allowed me to make this article and for making it a lot easier for me to learn about this.
Having started the journey of learning as much as I can about quantum computing, I decided that the next step is to try and gain an understanding of something practical. There has been a lot of discussion and debate about quantum computers having the potential to break encryption, thus rendering all internet encrypted traffic open to prying eyes, so I decided to investigate.
Fair warning, this is going to get a little complicated and I will try and explain it in layman’s terms, although there will be an equation or two involved – but nothing more complicated than middle school algebra … I hope.
All encryption over the internet is based on finding the
factors of a really large non-prime number. 
Unlike multiplying numbers together to get a really large number, dividing a really large number into integer factors takes a very long time. The best method we have for doing this is incredibly slow. In my previous article I mentioned that the largest factored RSA number was 768 bits long and it took 15,000 CPU years to decrypt (two years of real time, on many hundreds of computers). This takes too much time and electricity to be useful.
Enter Shor’s algorithm, quantum computers, and the threat these pose to effectively breaking encryption. The algorithm is based on two aspects of quantum theory, ‘quantum superposition’ and ‘interference’. Peter Shor is an American professor of applied mathematics at MIT and is the inventor of this quantum algorithm from his work in the 90s in the field of quantum computation.
RSA encryption is based on a mechanism of obscuring information with a large number such that the only way to unobscure it is by finding the factors of this large number. Our current best method effectively guesses a number and if it isn’t a factor, then it tries another until it finally finds a guess that works. Even with optimisations during the process, it is extremely slow.
Ultimately though, all encryption is based on the hope that the factoring process takes so long that people won’t bother and to date this has largely been the case.
Shor’s algorithm is based on making a bad guess of a factor and then using the algorithm to turn that bad guess into a much better guess. Unlike quantum computers that take an astonishingly small amount of time, classical computers can also run Shor’s algorithm but take a very long time to complete.
Fundamentally, it can be broken down into two parts:
- The mathematical part – making the guesswork more accurate; and
- The physics part – speeding up the process
The TL;DR here is roughly as follows:
- Make a guess, g, at a number that shares factors with the RSA encrypted number, N
- Shor’s algorithm says that a much better guess would be gp/2 ± 1, where P is the number of times you’d have to multiply g with itself such that
gp = m * N + 1, where m is some multiple of N - We can find P very quickly by using quantum superpositions and interference so that all the wrong superpositions of P destructively interfere with each other and you’re left with the right value
- Working this back we can then use Euclid’s algorithm to find the real factors
- Then we break the encryption!
The Maths Part
(NB: The following section uses * to symbolise multiplication – while this may offend the purist mathematicians for the purposes of this article it is being used due to common usage by non-mathematicians)
Let’s start with a big number N, which you’ll need to find the factors of. First step, make a guess, g, which is a number less than N. Numbers that share factors are okay too because of Euclid’s algorithm, which I won’t go into now, but effectively means that we can find the real factors using this.
We can now use a trick based on the following, to turn the bad guess into something more accurate:
Take any pair of whole numbers that don’t share a factor with N and multiply one of them by itself enough times you’ll eventually end up with some whole number multiple of the other number plus 1
Factor A * Factor B → A * A * A * A …(enough times) = some multiple * B + 1
Written more succinctly, this is:
AP = m * B + 1, for some power P and some multiple m. The important part here is that we eventually end up with a situation where we have a remainder of 1.
Let’s take a look at a few examples.
If we take 7 and 15 as A and B, then:
72 = 3 * 15 + 4
73 = 22 * 15 + 13
74 = 160 * 15 + 1 ← We have a good match!
Or looking at 42 and 13:
422 = 135 * 13 + 9
423 = 5699 * 13 + 1 ← And another match
Working this forward, for our big number N and some bad guess g, we are guaranteed that:
gp = m * N + 1
Being clever with our mathematics here, we can also write this as:
gp – 1 = m * N
Or be even more clever, by rearranging the algebra like this:
(gp/2 + 1) * (gp/2 – 1) = m * N
Now we have an equation which roughly looks like something * something = m*N, that is to say, the unknown factors. And even better, these two parts are in the format that Shor’s algorithm prescribes, which is to say, take a guess g, multiply it by itself p/2 times and then add or subtract 1:
g → gp/2 ± 1
In this equation, we now have a situation where each part can be a multiple of the actual factors we’re looking for and Euclid will come to the rescue so that we can find the real factors. Once we have them, we’ll have broken the encryption!
The Physics Part
(Note: The notation for a superposition is |something> where the something is a value, set of values or a function)
Now for the hard part, how to find P (i.e. the number of times we need to multiply our bad guess by itself to get: m * N + 1).
Unlike a normal computation – which gives one answer for a given input – a quantum computation can simultaneously calculate a whole load of possible answers for a given input by using a quantum superposition. Even better, all of those possible answers are whittled down to a single correct answer by destructive quantum interference (i.e. just like waves can destructively interfere with each other to cancel out). Let me try and explain one step at a time.
In general it can be very difficult to try and put anything into a quantum form where all the wrong answers destructively interfere, but that’s exactly what Shor’s algorithm does for the problem of finding P.
Just to recap, we’ve made a bad guess, g, and we’re trying to find P, such that gp = m * N + 1. A P that does that is also very likely to share factors with N (that is to say, gp/2 ± 1).
Next we need to build a quantum mechanical computer program that takes a number, x, as input and then raises our guess to the power of x. The program then needs to take that number and calculate how much bigger than a multiple of N it is, let’s call that the remainder.
|x> → qf(gx) → |x,gx> → qf(?>m*N) → |x,+r>, where qf is a quantum function, and the remainder, r, we’re looking for should eventually be 1.
As it’s a quantum computer we’re working on, we can send in a superposition of numbers instead of a single number to speed up the process. For example:
|1> + |2> + |3> + … → qf(gx) → |1,g1> + |2,g2> + |3,g3> + …
And then a superposition of how much bigger those powers are to the number:
→ qf(?>m*N) → |1,+19> + |2,+37> + |3,+23> + …
If we try to measure the superposition at this point we will run into trouble (we’re looking at the cat in the box) because the quantum state will collapse and return a random (and not necessarily the correct) answer. Instead, we need to get all the non-P answers to destructively interfere and cancel out, leaving us with only one possible answer, the true P.
Luckily, there is another mathematical trick that will allow us to do just that. So, again, let’s recap. If we knew what P was, we could raise our guess, g, to the power of P and get 1 more than a multiple of N:
gp = m * N + 1
If we take our guess to a random power, say 42, then it’s probably going to be some other number more than a multiple of N:
g42 = m * N + 7
Now here’s the interesting part, if we raise our guess to the power of that random number (42) plus P then it will be the same remainder with a different multiple:
g42+p = m2 * N + 7
Notice that the remainder is always the same no matter what multiple of P we add to our random number x:
gx = m * N + r
gx+P = m2 * N + r
gx+2P = m3 * N + r
gx+3P = m4 * N + r
Etc.
Effectively, P has a repeating property to it such that if we take our guess and raise it to the power of a random number and then add multiple Ps to it then the remainder stays the same.
gx or gx+P or gx+2P or gx+3P or … ⇒ +r (r is always the same)
This repeating pattern isn’t something you can figure out by taking our guess to just one power. Rather it’s a structural relationship between different powers and we can take advantage of it because quantum computations can take advantage of superpositions of different possible powers.
If we take the superposition of all possible powers and just measure the amount more than a multiple of N part (the remainder, +r), then we are left with a superposition of just the powers that could have resulted in the same remainder.
The key part here is that each of these superpositions are exactly P apart from each other! These superpositions repeat with a period of P, or to be more specific, have a frequency of 1/P. If we can find the frequency, we can find P and break the encryption. Luckily, we have a tool to find frequencies: the Fourier Transform.
Fourier transforms are a way to input a signal, say an audio signal for example, and they will produce a graph of all the frequencies that the signal is made up of. This is how noise-cancelling headphones work, they select the frequencies from the surrounding environment using a Fourier transform and cancel them out using wave interference. Very clever stuff.
To solve our problem here, there is a quantum version of the Fourier transform, which we can apply to our superposition and find P. In a nutshell, it causes all the possible values that aren’t correct to destructively interfere so that we are left with the correct frequency 1/P.
Now that we have 1/P, we can invert that to get the value for P (i.e. 1/1/P). As long as that is an even number, we can put that back into our equation gP ± 1, and as long as that is not a multiple of N, we are guaranteed that it shares a factor with N. We can then use Euclid’s algorithm to find the real factors of N and finally break the encryption!
Next Steps
We have quantum computers today, so what’s stopping us from breaking encryption right now? In a nutshell, the size of quantum memory in these computers. This is still an emerging field of research and although some quantum computers exist, they have nowhere near enough quantum memory yet to be able to make the calculations necessary to break encryption. Some estimates say that around 5096 qubits are required to break the 768-bit RSA encryption in the example given above. Currently, we’re in the 10s of qubits – a long way off.
Saying that, a lot of time and money are being poured into this field and developments are gathering pace. What is certain however, is that quantum computers WILL eventually break encryption so the roll out of better encryption is essential in combating this and keeping our private information truly private.
