Papers of the day   All papers

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

Comments

Conner Brown: If you’re worried about quantum cracking ECDSA after the Google announcement (like I was), here’s some perspective: State-of-the-art quantum computers are ~50 qubits. The amount required to derive your private key is ~20 million qubits. https://arxiv.org/pdf/1905.09749.pdf

2 replies, 158 likes


Craig Gidney: This is the paper that was split into four: https://arxiv.org/abs/1905.09749 "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Combines improvements from the other papers into >100x less spacetime. Previous comparable results took a billion qubits over a day. https://t.co/D6Iucp9bDE

12 replies, 135 likes


Binni Shah: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits : https://arxiv.org/pdf/1905.09749.pdf (pdf)

1 replies, 74 likes


Peter McMahon: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 -- the perfect paper to send anyone who asks how far away we are from seeing a quantum computer break 2048-bit RSA

2 replies, 59 likes


Quantum Bullshit Detector: Not Bullshit.

3 replies, 28 likes


dabacon: A factor of a hundred here, a factor of a hundred there. Next thing you know we'll have factored faster.

0 replies, 28 likes


mjos\dwez: Craig Gidney, Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Looks to me like their physical and algorithmic QC design is at pretty advanced state? https://arxiv.org/abs/1905.09749

3 replies, 17 likes


Alfonso Muñoz: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits - https://arxiv.org/abs/1905.09749

1 replies, 14 likes


Ion busters: The papers keep coming from @arXiv_quant_ph today! Next up @CraigGidney discusses how you can factor a 2048 bit RSA integer in 8 hours using 20 million noisy qubits. https://arxiv.org/pdf/1905.09749.pdf We always used to tell people it took billions and years from https://bit.ly/30PZ2v0 ! https://t.co/7DpobYw9ZC

0 replies, 7 likes


Jacopo Bertolotti: "Although Shor’s algorithms run in polynomial time, the constant factors hidden by the asymptotic notation are substantial." (From: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits": http://arxiv.org/abs/1905.09749 )

2 replies, 6 likes


Noclone3: Added to the papers I must read #RSA #quantum #qubit

0 replies, 6 likes


Joeri Beerts: End of the password. By using quantumcomputing, a 2048bit RSA- encrypted password can be hacked in 8h. https://arxiv.org/pdf/1905.09749.pdf

0 replies, 5 likes


Sam Bowne: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019) https://arxiv.org/pdf/1905.09749.pdf

0 replies, 4 likes


Enrique Solano: Check this 2019 article https://arxiv.org/abs/1905.09749 The number of qubits in a quantum computer depends on the problem encoding, overhead, ancillas, error correction, physical, or logical qubits. You can find 65 qubits @ibm and struggling to compare power with 5,000 qubits @dwavesys

1 replies, 4 likes


Guillaume Verdon: @jpdowling @MJBiercuk I would say we need 18±4 years at the current rate of qubit count exponential growth. https://arxiv.org/abs/1905.09749

1 replies, 3 likes


Arrigo Triulzi: C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits” […abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3n+0.002nlgn logical qubits…] https://arxiv.org/abs/1905.09749

0 replies, 3 likes


Alan Woodward: Orders of magnitude improvement in factoring 2048 but it’s still 20million qubits (optimistically) so don’t panic just yet https://arxiv.org/pdf/1905.09749.pdf

0 replies, 2 likes


QRAvalanche: The #SecretaryOfQuantumComputers has been contacted again by the press, on the recent #quantumcomputing breakthrough: https://arxiv.org/abs/1905.09749 #QRL $QRL @QRLedger #quantum #bitcoin #ecdsa https://t.co/F9DeEcGB8a

0 replies, 2 likes


Jacky Martin: A more efficient method for factoring 2048 bit RSA integers, interesting if you are into Quantum Physics: https://arxiv.org/abs/1905.09749 This will become more important for cryptographic codes protecting sensitive information. https://arxiv.org/abs/1008.2390

0 replies, 2 likes


snannerb1: @Jason Just read through all these replies and not a single mention of the fact that quantum computers have and will continue to advance with time , https://mobile.twitter.com/peterlmcmahon/status/1131728997627203584 ... there is quantum resistant crypto out there and encryption is what holds this all together.

0 replies, 2 likes


Johannes Jakob Meyer: @fwilhelm @KikeSolanoPhys The 20 million are due to Craig Gidney: https://arxiv.org/abs/1905.09749

0 replies, 2 likes


Noclone3: @APompliano This one by a Google researcher on an accelerated Shor algorithm for breaking RSA (with future quantum computers) https://twitter.com/CraigGidney/status/1131720243376558080

0 replies, 2 likes


Enrique Solano: Yes, it is public, co-authored by a brilliant quantum computing colleague @CraigGidney and good soccer pal @GoogleAI I just try not to represent or involve others in my opinions and proposals that may be considered a discrepancy with mainstream ideas.

0 replies, 2 likes


Gavin Crooks: A superconducting qubit is about 1mm on a side. If you stacked them 3d they would be about 1mm apart. That's about 1 million qubits per liter. So factoring 2048 bit RSA will need about 20,000cc of qubits. We're going to need a bigger dilution refrigerator.

0 replies, 1 likes


Noclone3: @duganist And here is a "practical" implementation that you may love too https://arxiv.org/abs/1905.09749

0 replies, 1 likes


Andrei ILchenko: I like how Bruce Schneier put, “Our work on quantum-resistant algorithms is outpacing our work on quantum computers” https://www.schneier.com/blog/archives/2019/10/factoring_2048-.html in response to this paper: https://arxiv.org/abs/1905.09749 on factoring 2048 bit RSA moduli

0 replies, 1 likes


HotComputerScience: Most popular computer science paper of the day: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://hotcomputerscience.com/paper/how-to-factor-2048-bit-rsa-integers-in-8-hours-using-20-million-noisy-qubits https://twitter.com/CraigGidney/status/1131720243376558080

0 replies, 1 likes


Content

Found on Sep 28 2019 at https://arxiv.org/pdf/1905.09749.pdf

PDF content of a computer science paper: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits