Cryptographers HATE it!
Too much math; didn’t read — Shor’s algorithm doesn’t brute force the entire key by trying factors until it finds one, but instead uses the quantum computer to find the period of a function which contains the RSA key and classically computes the greatest common divisor.
RSA encryption is strong because factoring is a one-way problem. It’s very easy to multiply two primes together, but very difficult to find prime factors of a large number. That’s what the technology relies on. And the simplicity of RSA encryption made it very popular.
However, one technology can render RSA useless.
(Hint: it’s a quantum computer)
Shor’s algorithm can crack RSA. But how does it really work? It’s not about trying all prime factor possibilities simultaneously.
In (relatively) simple language: We can crack RSA if we have a fast way of finding the period of a known periodic function f(x) = m^x (mod N)
Five Steps of Shor
So how does Shor’s algorithm work? In the five steps of Shor’s algorithm, only ONE requires the use of a quantum computer. The other steps can be solved classically.
Step 1: use the classical greatest common divisor (gcd) algorithm on N and m, where N is the number you are trying to factor, and m is a random positive integer less than N.If the gcd(m, N) = 1, continue. If you find a factor using gcd, you’ve found a non-trivial factor and are done.
Step 2: find the period P of:
m mod N, m^2 mod N, m^3 mod N
This is the quantum step
Step 3: if the period P is odd, go back to step 1 and choose another random integer. Otherwise, continue
Step 4: check that
If that is true, go to Step 5
Otherwise, go back to Step 1
Step 5: Solve
The answer is a non-trivial prime factor of N, and you now have the key to break RSA.
How does Step 2 work?
But how does a quantum computer find the period of the function, as in step 2? And why is this important?
We are looking for the phase (period P) of
m mod N, m^2 mod N, m^3 mod N
(While this is an exponential function, we can transform a complex exponential into hyperbolic sin and cos and get a periodicity)
This period finding step relies on the quantum superposition. With a quantum computer and its ability to be in a superposition of states, we can find the period of the function. To do so, we:
1. Apply the Hadamard gate to create a quantum superposition
2. Implement the function into a quantum transform
3. Perform the quantum Fourier transform.
Like it’s classical analog, after these transformations, a measurement will yield an approximation to the period of the function (you can read the ‘peak’, like in the classical Fourier transform, with a high probability). Using the quantum Fourier transform, we can solve the order-finding problem and factoring problem, which are equivalent. The quantum Fourier transform allows a quantum computer to perform phase estimation (the approximation of eigenvalues of a unitary operator).
As you exit the quantum portion (step 2), you check the period for validity and use another classical greatest common divisor algorithm to get the prime factor of the key.
Interestingly enough, since the technique is not about trying all the potential prime factors, just the potential periods, you do not have to try many random numbers to successfully find a prime factor of N. The probability that P is odd, and you have to return to step one, is
where k is the number of distinct prime factors of N. So even if you double the key length (N), there will not be a slowdown in finding the factors. RSA is not secure and doubling key size will not help in achieving a level of safety against a quantum adversary.
The RSA-2048 Challenge Problem would take 1 billion years with a classical computer. A quantum computer could do it in 100 seconds
-Dr. Krysta Svore, Microsoft Research
The quantum Fourier transform is applied to a quantum circuit built just out of 1 qubit and 2 qubit gates, making the physical implementation of Shor’s algorithm one of the easiest tasks for a quantum computer.
Beyond Shor
The quantum Fourier transform is the key to many of these quantum algorithms. It doesn’t speed up finding classical Fourier transforms, but can perform a Fourier transform on a quantum amplitude. It is exponentially faster to solve the quantum Fourier transfer on a quantum computer. Though there are subtleties beyond directly mapping classical Fourier transform problems, a quantum computer can also, for example, solve the hidden subgroup problem, which solves the discrete logarithm problem, or counting solutions, which crack other forms of modern cryptography. More importantly, the quantum Fourier transform can be applied to machine learning, chemistry, materials science, and, obviously, simulating quantum systems.
At the core of Shor’s factoring algorithm is order finding, which can be reduced to the Abelian hidden subgroup problem, which is solved using the quantum Fourier transform.— NIST Quantum Zoo
Just one of the steps of Shor’s algorithm needs to be implemented on a quantum computer, while the rest can be done on a classical supercomputer. The quantum subroutine will be performed and fed back to the supercomputer to continue the calculation. A quantum computer will likely never be a standalone system, but together with a supercomputer, the time to break an RSA key will be quite reasonable.
There are a lot of mathematical details that have been glossed over, as well as the proofs of these steps as it is beyond the scope of this article. If you’re curious about the mathematical explanations, with intense linear algebra, group theory, and higher level mathematics, check out these sources:
Quantum Information and Quantum Computation
NIST Quantum Zoo — http://math.nist.gov/quantum/zoo/ — a list of all the quantum algorithms
