Mathematically/Theoretically calculating time to brute-force RSA encryption keys for a quantum computer vs a Classical computer?

Question

1. Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys?

I know there is a way to do so with a classical computer and time taken to brute-force RSA keys, but I'd like to specifically know how one calculates the time.

Furthermore, since the technology for brute-forcing RSA keys with a quantum computer differs from the one of a classical computer; How would one calculate the time to brute-force RSA keys using a quantum computer?

2. To do the calculation I'm guessing you have to take into consideration the amount of computing power. If possible use (or give me an example of) what equal (ish) computing powers in-between Classical and quantum computers would be. For example what scale classical computer is needed to compare (and be on the same level) as a 5-qubit quantum computer (only) in terms of brute-forcing RSA keys?

Answer 1

Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys?

Even classically, this is not so easy as you seem to imply.

RSA is based on the hardness of the integer factorization problem. The fastest classical algorithm known that solves this problem is the General Number Field Sieve (GNFS), and it solves integer factorization in subexponential time, or $\exp((\sqrt[3]{64/9}+o(1)) (\log N)^{1/3} (\log \log N)^{2/3})$ where $N$ is the modulus, and $\log$ refers to the natural logarithm.

However, we can't easily calculate an exact running time using this formula. Asymptotic running times hide constant values, which can vary wildly depending on the algorithm. Additionally, they don't tell us anything about what kind of parallelization may be possible.

GNFS happens to be a very complex algorithm. It involves a significant number of parameters. There are four different "stages" to the algorithm. Some stages can be made to take more time, in order to make the other stages faster. Additionally, some stages are easily parallelizable, while others are not, or only to a limited degree. In other words, coming up with the right set of parameters in order to minimize the total time to break an RSA modulus is very far from trivial. Let alone somewhat accurately estimate how much time it will take.

So unfortunately there's no easy answer to this question. However, you can get an idea by looking at some numbers that have been successfully factored.

How would one calculate the time to brute-force RSA keys using a quantum computer?

This is easier to calculate but at the same time impossible. Integer factorization can be done using Shor's algorithm on a quantum computer. This algorithm runs in polynomial time, $O((\log N)^2 (\log \log N) (\log \log \log N))$. From this paper you can see that the number of logical qubits required are approximately $2 \log N$, and the number of logical quantum gates $4(\log N)^3$.

As mentioned in the paper, these logical qubits and quantum gates would require many physical qubits and quantum gates to actually implement. It's still not certain whether quantum computation is even possible on a large scale, due to issues with quantum decoherence. So again, I'm afraid there's no answer to this question. How could you possibly estimate the running time of an algorithm on a computer that doesn't yet exist?