Shor’s Algorithm- Decrypting RSA with Quantum
You’re watching a spy movie. The secret agent has 1 minute to decrypt the message to save the country from an incoming attack. He whips out his computer and smashes the keys on his keyboard. He exclaims, “Dammmit I can’t get past this firewall!” More key smashing. And just when his time is almost up, he hits enter. Boom. He has now saved the entire country.
Well, in reality, breaking current encryption messages isn’t that easy. But could it be?
Currently, RSA protocol is the standard encryption method given by the National Institute of Standards and Technology. At its heart, the encryption method relies on the fact that it is pretty difficult for computers to efficiently find the two prime factors of a large number. Right now, computers basically guess and check until they get the right answer.
However, in 1994 Peter Shor was able to come up with an algorithm that used the power of quantum computers to be able to calculate these prime factors much more efficiently. The algorithm makes use of two useful quantum properties- superposition and destructive interference, to essentially make random guesses into really good guesses.
The rest of the article gets more technical, but if a 15-year-old can write it, you can understand it. (There is a summary of the steps at the bottom of the article)
Given you have the number you want to factor, N, and a guess g where g<N: you can use something called Euclid’s algorithm to find the prime factors as long as g and N share common factors.
We also are given that, if you take two numbers (A and B) who don’t share any common factors, there is a value p where:
I am not going to prove that is the case, but you can pick any two random numbers and there will always be an exponent of the first number that is one more than some coefficient times the second number.
If we substitute A with our guess (g) and B with the number we are trying to factor (N), we can simplify the equation to the following:
For the purpose of this article, let’s define N (the number we want to factor) as 15. Let’s also use a random number less than 15, g=7, as our initial guess.
Once you find p, solving for g will give you a pretty good chance at guessing correctly for a prime factor of N. However, finding p is not an easy task. It’s not any easier, or maybe even harder, for a computer to try to find it compared to just guessing for g. However, this is where quantum magic comes in.
Let us leave that equation in the back of our minds for now. We want to optimize quantum algorithms so that they are more efficient than regular computers. We can’t just input a superposition of a bunch of numbers and receive a bunch of answers- as measuring it would collapse it down to one output. What we need to do is input a superposition of inputs and then make them “destructively interfere” with one another to boost the probability of getting the best answer.
To find p, let's input a guess |x> to our algorithm. The algorithm should take x and find
so its stores |x, +r> for a superposition of a bunch of different x values.
*note that the kit symbol |> signifies a quantum state
For our example of N=15 and g=7, testing different x values gets you the following:
Once you start testing a bunch of x values, you notice a pattern where different x values that have the same remainder are separated by a period, which is our p value:
|x, r>, |x+p,r>, |x+2p,r>..|x+ap, r> where r is the same in all of them.
In the case of our example, from our table above we can see that taking any r value (such as 7) gives you a period of 4. In other words, the remainder repeats every 4 values of x.
This p value is what we are trying to solve for, and we do that by using something called a Quantum Fourier Transform…
Let’s say that you have one number |a> that you input into the Quantum Fourier Transform, the output (graphically) would be a sinewave with a frequency of a and a period of 1/a.
And if you input a superposition of different values, you get a superposition of a superposition where the sinewaves can either destructively interfere with one another or amplify each other.
If you input a superposition of values separated by a value of p, the sinewave destructively interfere with another (note that this is oversimplified) to give you a period of 1/p or a frequency of p
If we input our guesses x and our remainders r from our example with 15, the superpositions of each |x,r> would destructively interfere with one another to get us 1/4, or p=4
Finally, if p is even, you can plug it into our original equation:
to get a number that has a common factor with N.
We can then use Euclid’s algorithm to finally our two prime factors of N and break the RSA encryption.
With our example where N=15, g=7, and p=4, we can simplify the right-hand side of the equation to be 50, and find the GCF(15,50) to be 5. Simply calculating 15/5 gets us our two prime factors: 3 and 5.
Taking a step back we…
1) took our number that we wanted to factor- N
2) Gave a random guess g and derived how to make our guess (g) “better” to make it share a factor with N
3) To find p, we first inputted a superposition of x values and took all the x values with the same remainder
4) We then stuck that into a Quantum Fourier Transform to make the sinewaves of these values destructively interfere to give us the frequency p
5) If the p value was even, we plugged it into the original equation and used Euclid's algorithm to derive the 2 factors of N
- Note that this won’t necessarily give you an answer on the first try- however, it gives you a pretty good chance, making it worth iterating and better than guessing and checking literally every prime number with a computer
Thank you for reading my article! You can connect with me on my LinkedIn or email me at lohitpotnuru@gmail.com. Sign up for my monthly newsletter here
