I've been reading about quantum computing and turns out that 512-bit quantum processors are already a thing. I also read about Shor's algorithm, which can break RSA and several asymmetric encryption schemas in the next upcoming years.

Quantum computing power has been growing faster than Moore's law and now I wonder how many qubits Shor's algorithm needs to factor 2048-bit key modulus.

Source: https://www.youtube.com/watch?v=6VIAL8gQRTI

  • 2
    Something around 4000 ideal qubits should be enough. In practice you'll need a lot for the error correction. Luckily the best real quantum computers (not dwave bullshit) still limited to 5 qubits or so. – CodesInChaos May 2 '15 at 14:19
  • Why are dwave's quantum computers bullshit? Can't they used to crack RSA? – Nacib Neme May 2 '15 at 14:44
  • 2
  • D-Wave is a quantum computer, but it is not a cryptoanalytic quantum computer. It can solve different problems. Recently (in the last year or two), it was demonstrated to actually have some properties of a quantum computer, but it will never be able to run Shor's algorithm. – forest Feb 3 at 6:06
up vote 16 down vote accepted

Actually the question must be clarified, that in which time you want to break RSA, for example scientists say that RSA with 512-bit can be broken in 6 week with quantum computers, but with how many qubits? So time is important, 2 qubit can break 2048-bit but in which time? Because in quantum computers each qubit can be 0 and 1 in each moment, so n qubit can handle 2n state in a moment, if number of qubits are increased the break time decreases(reverse relation). For example 2048 qubit can handle 22048 state in moment. Also only qubits are not enough, qubits are memory for quantum computers. More qubits mean you can factor bigger numbers.

According to mentioned paper:

... If large quantum computers can be built, then RSA ciphers become useless. It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years.

Quantum Computing and Cryptography

And according to this one:

Quantum memory units are called qubits and the largest quantum computers capable of running Shor’s algorithm only have about 20 qubits. (A Canadian company called DWAVE has a quantum computer with 512 qubits but it has very high error rates on its qubits and is based on another principle called quantum annealing.) To run Shor’s on 2048 bit RSA would require at least 10,000 qubits. It will probably be a while before such a machine can be built.

Online security, cryptography, and quantum computing

  • The problem is error correction, which currently require (the latest D-Wave 2X) to use ~12 physical qbits for every logical qbit. For example, in this [2016] paper they manged to factor 200,099 = 499*401 using 897 physical qbits in 3.5 seconds. (We estimate that an RSA-1024 factor can be up to ~309 decimal digits long.) – not2qubit Feb 3 '17 at 16:10
  • 3
    You cannot run Shor's algorithm on a D-Wave (crypto.stackexchange.com/questions/40893/…). You can do factorisation with quantum annealing (physics.stackexchange.com/questions/11063/…) but the complexity is not the same. – Francis Davey Jul 18 '17 at 18:21
  • The best implementation of Shor's algorithm on an n-bit semiprime requires 2n + 3 logical qubits. – forest Jun 12 at 4:27

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.