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. May 2, 2015 at 14:19
  • Why are dwave's quantum computers bullshit? Can't they used to crack RSA?
    – Nacib Neme
    May 2, 2015 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, 2018 at 6:06

2 Answers 2


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

  • 3
    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, 2017 at 16:10
  • 4
    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. Jul 18, 2017 at 18:21
  • The best implementation of Shor's algorithm on an n-bit semiprime requires 2n + 3 logical qubits.
    – forest
    Jun 12, 2018 at 4:27
  • 1
    It's important to notice that the current best result (factor 200099) means that best quantum computers can execute Shor's algorithm for up to 18 bit number. To put this into perspecitive, to factor that number with classical computer, the most simple algorithm would be to just try every odd number between 3 and square root of 200099 or 447. For this example, it requires doing maximum of 447/2 divisions which can be executed in around 1341 CPU clocks (modern CPUs have effective throughput of about 6 clock cycles per division). That requires about 260 ns or 0.00000026 seconds in total. Apr 13 at 11:13
  • 1
    @Mikko Rantalainen Taking into account, that measurement errors grow exponentially with the number for Q-Bits, this implies that ´Shor's algorithm won't be a security threat for long time´. Apr 14 at 14:19

According to latest publications:

Equivalent (classical) bit-security Minimum qubits needed to attack RSA, DSA etc Minimum qubits needed to attack ECDSA and similar EC schemes
112 4098 (RSA 2048) 2042 (ECC 224)
128 6146 (RSA 3072) 2330 (ECC 256)
192 15362 (RSA 7680) 3484 (ECC 384)

Source: Quantum Attack Resource Estimate: Using Shor’s Algorithm to Break RSA vs DH/DSA VS ECC

  • This answer could be improved by indicating if these are physical or logical qubits. These are logical qubits, you may need hundreds or possibly thousands of qubit per logical qubit to make this work (the error correction circuits have improved as well). Of course, current quantum computers are measured in physical qubits. The article is well worth the read, although I would have preferred it in peer review paper form of course. Apr 15 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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