Breaking RSA Using Shor's Algorithm
buttons.Abstract
Use this article to see a quantum implementation capable of breaking RSA. Like classical complexity theory, quantum complexity is measured based on the number of gates in a quantum circuit and the time complexity. Try to gain an understanding of the complexity measures presented in this article.
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor
1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Eker˚a-H˚astad 2017, Eker˚a 2017,
Eker˚a 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of
our construction using plausible physical assumptions for large-scale superconducting
qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10−3, a surface code cycle time of 1 microsecond, and
a reaction time of 10 microseconds. We account for factors that are normally ignored
such as noise, the need to make repeated attempts, and the spacetime layout of the
computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works. In the abstract
circuit model (which ignores overheads from distillation, routing, and error correction)
our construction uses 
logical qubits, 
Toffolis, and
measurement depth to factor n-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP
in finite fields.
Source: Craig Gidney and Martin Eker, https://quantum-journal.org/papers/q-2021-04-15-433/pdf/
This work is licensed under a Creative Commons Attribution 4.0 License.