Breaking RSA¶
Let’s sketch the Shor algorithm!
Quantum Fourier transform¶
We start with the quantum Fourier transform, which is a linear operator in an \(N\)-dimensional Hilbert space. Let \(\ket{0}, ..., \ket{N - 1}\) be an orthonormal basis of this space, the QFT is defined as
i.e. it associates to an element of the basis a superposition of all the basis elements.
To any arbitrary state \(\sum_{j=0}^{N-1} x_j \ket{j}\) the QFT assigns a state \(\sum_{k=0}^{N-1} y_k \ket{k}\) whose amplitudes are the DFT coefficients of the amplitudes \(x_j\).
It is very useful to note that a system of \(n\) qubits evolve in a \(N = 2^n\)-dimensional space, i.e. we can write the elements \(\ket{j}\) above using a binary representation \(j = j_1 j_2 ... j_n\). This representation can be used to construct an efficient quantum circuit computing the QFT with a complexity of \(O(n^2)\) in terms of gates 1.
Phase estimation¶
Let \(U\) be an unitary operator and \(\ket{u}\) one of its eigenvectors with eigenvalue \(e^{2 \pi i \phi}\). The purpose of the phase estimation algorithm is to estimate \(\phi\) by an approximation \(\widetilde{\phi}\).
It makes use of two registers, where the first one is initialized in state \(\ket{0}\) while the second one is in state \(\ket{u}\) i.e. we start from \(\ket{0} \ket{u}\). By applying Hadamard gates on each qubit of the first register, we generate a superposition of “all the possible” states, apply \(U\) a certain number of times on the second register (this is the real magic), and apply the inverse Fourier transform, to finally terminate in state \(\widetilde{\ket{\phi_u}} \ket{u}\).
This is a product state (no entangled superposition), thus we just have to measure the first register to get \(\widetilde{\phi}\)! Well, we get this value only with some probability, but this can be managed to be arbitrary close to one.
Order finding¶
Now a bit of arithmetics.
For positive integers \(x\) and \(N\) with \(x \lt N\) and no common factors, the order of \(x\) modulo \(N\) is defined to be the least positive integer, \(r\), such that \(x^r = 1 \, (\mathrm{mod} \, N)\). Order finding is the task of finding \(r\) for given \(x, N\), and is believed to be hard for a classical computer in terms of the size \(L = \log(N)\).
One can show that order-finding is equivalent to the phase estimation algorithm applied to the unitary operator \(U \ket{y} = \ket{ x y \, (\mathrm{mod} \, N) }\). Indeed the eigenvalues of \(U\) are the numbers \(\exp{ \frac{2 \pi i s}{r} }\) with \(0 \le s \le r - 1\). This means, if we could prepare the second register in the state of an eigenvector \(\ket{u_s}\) of \(U\), and we could implement \(U\) efficiently, we would have an estimation of \(\frac{r}{s}\). But then we must still find a way to derive \(r\)…
Lot’s of obstacle…
First notice that
i.e. we can perform the phase estimation procedure on \(\ket{1}\) and will get an estimation of one of the \(\widetilde{\phi} = \frac{s}{r}\).
The implementation issue of \(U\) can be solved using a procedure known as modular exponentation, that we won’t detail here.
But how can we recover \(s\) and \(r\) from \(\widetilde{\phi}\)? A remarkable algorithm called the continued fractions algorithm allows us to find a continued fraction expansion of an arbitrary real number. In our case, we are looking for the expansion of a rational number, described by L digits. The algorithm scales as \(O(L^3)\). Thus, we have a way to calculate \(r\), since \(s\) and \(r\) have no common factor!
Factoring¶
Factoring can be reduced to order-finding by an algorithm scaling as \(O((\log N)^3)\) with probability \(O(1)\). After a few preliminary steps for finding easy factors of \(N\), one of the steps of the algorithm involves choosing randomly a number \(x\) in the range \(1\) to \(N - 1\), using the order-finding subroutine to find the order \(r\) of \(x\) modulo \(N\). Then (omitting additionaly checks) the gcd of \((x^{r/2} - 1, N)\) and of \((x^{r/2} + 1, N)\) are calculated: If one of these is a non-trivial factor, then we have found the result!
RSA problem¶
Wikipedia tells us: “The RSA problem is defined as the task of […] recovering a value \(m\) such that \(c = m \, e \, (\mathrm{mod} \, n)\), where \((n, e)\) is an RSA public key and \(c\) is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus \(n\).”
Et voilà!
Conclusion¶
The Shor algorithm has a proven capacity of breaking the RSA cryptosystem in polynomial time. But how many qubits will we need for this task?
The NIST recommends RSA key sizes of 2048 bits. Bytheway you may click on your browser’s lock symbol close to the address bar and check yourself the size of your current RSA encryption.
That means we will need 2048 qubits just to store the number to factorize. Depending on the error correction algorithms (just think of a repetition code that requires many physical qubits to implement one logical qubit), many more qubits will be necessary. But it was shown that about 20 million qubits, much less then previously thought, could be enough to factorize the 2048 bit number in 8 hours [43].
But how to achieve a quantum computer with so many qubits, that would achieve such an incredibly long coherence time? We still need some technological breakthrough…
- 1
We can interpret the QFT as a mapping from and to a N-dimensional space. Because a set of \(n\) qubits evolve in a space of dimension \(N = 2^n\), the QFT’s complexity can be written in terms of \(n\). It can be shown that the QFT can be implemented by a quantum circuit using \(O(n^2)\) elementary gates, i.e. \(O((\log{N})^2)\)
For comparison, the classical Discrete Fourier Transform (DFT) with N terms has a complexity of \(O(N^2)\), and the Fast Fourier Transform (FFT) scales with \(O(N \log{N})\).
Thus one could imagine that the QFT would represent an exponential speedup compared to the FFT, as \(O(N \log{N}) = O(2^n n)\). But the FT and the QFT achieve two different goals: while the FT returns the \(N\) coefficients as numbers, the QFT generates a superposition of states whose amplitudes are the Fourier coefficients.
Complements: An Introduction » Quantum Computing » Applications