How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

Question

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a few years. With Shor's algorithm, elliptic curve cryptography will likely be the first to fall as it has lower key lengths and therefore a lower number of qubits are required to break it. If using RSA with larger key sizes e.g. 2048 bits, this may buy a few more years of time, hopefully then a transition to post-quantum algorithms can be made.

Does anybody know:

1. How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?
2. How many qubits are required to break Curve25519?
3. I want to work out the relationship between the key length and number of qubits required to break that key length. Is there a simple layman's formula for working out how many qubits are required using the number of key bits and number of qubits as inputs into the function? E.g. n = number of public key bits, q = number of qubits the machine has, a = the answer (number of qubits required to break it). Maybe the formula is just a = n = q, i.e. 2048 qubits are required to break RSA 2048.

If you can prove your answer with citations to any papers or research that would also be beneficial.

Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?

Answer 1

1. How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?

Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit.

This paper (PDF) has an algorithm using $2n+3$ qubits, where $n=\log_2 (N)$, where $\log_2(N)$ is the way to calculate the number of bits in $N$.

2. How many qubits are required to break Curve25519?

Breaking elliptic curves requires (pdf, see 6.2) roughly $6n$ qubits where $n$ is the order or key size of the curve, which for Curve25519 would be $6 * 255 = 1530$. Less than secure RSA sizes require, but much more than has been accomplished.

3. I want to work out the relationship between the key length and number of qubits required to break that key length.

See above.

---

Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?

You are using the wrong value for $N$. It is the modulus, not the bit length. The actual number of qubits needed for 2048-bit RSA is about 4096.

---

Note (from removed comment to the present answer): We're talking about ideal qubits here. Error correction might increase the number of physical qubits beyond these numbers.