How to factor 2048 bit RSA integers in 8 hours using 20M noisy qubits

I'm one of the authors on this paper and can answer questions if people have some.

How plausible is it that someone could acquire this many qubits? How many doublings away are we?<p>EDIT: [1] suggests D-wave could be 5640 by 2020, doubling approx. every two years - 12 doublings = 24 years from now.<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;D-Wave_Systems#D-Wave_2X_and_D-Wave_2000Q" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;D-Wave_Systems#D-Wave_2X_and_D...</a>

I haven&#x27;t finished reading the paper, but maybe my biggest immediate takeaway is that significantly increasing the number of bits doesn&#x27;t really help. Using the methods discussed in the paper, 4096 bit integers can be factored in less than 4x the amount of time needed to factor 2048 bit integers. In other words, should this method become practical, cryptographers couldn&#x27;t solve the problem by using integers we would ordinarily consider much harder to factor.

<a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1905.09749" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1905.09749</a>

It doesn&#x27;t look like there is even a need for quantum proof algorithms. An Epyc CPU with 32 cores has 20 billion transistors. Even if we can build qubits as tiny as a transistor you won&#x27;t be able to break RSA with ridiculous key lengths above 2000000 bits. In reality qubits will be bigger than transistors, not all quibits can be active at the same time and there won&#x27;t be the same exponential growth in the number of qubits as we have seen in conventional computers.

Relevant presentation on real world cipher reversing with quantum computing:<p><a href="https:&#x2F;&#x2F;www.phdays.com&#x2F;en&#x2F;program&#x2F;reports&#x2F;reversing-cryptographic-primitives-using-quantum-computing&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.phdays.com&#x2F;en&#x2F;program&#x2F;reports&#x2F;reversing-cryptogr...</a><p>Slides: <a href="https:&#x2F;&#x2F;speakerdeck.com&#x2F;rlifchitz&#x2F;ordinateurs-quantiques-et-futur-de-la-securite" rel="nofollow">https:&#x2F;&#x2F;speakerdeck.com&#x2F;rlifchitz&#x2F;ordinateurs-quantiques-et-...</a>

How likely is it that for breaking 2048 bit RSA integers you&#x27;ll just need 2048 unnoisy qbits?<p>That this lowered 20M requirement is just ploy to keep people using 2048 bits, not 4K as required by GNU. It is my understanding that 2048 qbits are already in reach to well-funded state agencies.

So, is there some alternative quantum-resistant cipher ready (i.e. with open source implementation, say on github) that we can use today to encrypt out long-term secrets?

So RSA has some 10-20 years to go. Is there a quantum computing-proof encryption algorithm, or is it just a matter of increasing key lengths?

Is this the long fabled quantum computing application that breaks asymmetric cryptography?