# Quantum vs. regular computing time to break ECC?

How long exactly would it take for a regular computer to crack an elliptic curve public/private key via bruteforce, vs. a quantum computer using Shor's algorithm with a couple thousand qubits? Can anyone reference me a source?

I'm assuming the digital computer will take thousands of years, but how long exactly is the polynomial time achieved by theoretical quantum computers?

## 1 Answer

It's hard to answer given that there is no quantum computer to perform benchmark on. However, let us assume a quantum computer which would perform quantum operations as efficiently as our current standard computer can perform classical operations (this might be a bit unrealistic but it's hard to come out with realistic assumptions regarding quantum computing given the state of advancement of this research field). The complexity of Shor's algorithm being $O(\log^2 n \log \log n \log \log \log n)$ according to Wikipedia, one can observe that this is better than the complexity of the best known classical algorithms for performing the multiplication of two $\log n \times \log n$ matrices. A quick search over some papers such as this one indicates that an optimized implementation of matrix multiplication of size $1024\times 1024$ can take less than a second, hence it does not seem unreasonable to assume that if a quantum computer was executing an optimized implementation of Shor's algorithm, factorization of a 2048 bit integer would take very little time - say, less than a few minuts.

For a regular computer performing a discrete logarithm over an elliptic curve is not done with brute force as you suggest, but using the Rho-Pollard algorithm, whose complexity is $O(\sqrt{p})$, where $p$ is the order of the curve. Still, executing this algorithm on well-chosen curves of size higher than $256$ bits is completely impractical.

• "Still, executing this algorithm on well-chosen curves of size higher than 256 bits would take at least several years". Eh, sorry, but who's choosing the curves here? $\sqrt p$ where $p = 2^{256}$ would still leave you with $2^{128}$ right? Are you saying that you expect that to run "at least several years" on classical computers? And if so, are you employed by the NSA? – Maarten Bodewes May 17 '16 at 22:59
• @GeoffroyCouteau, I think the point was that even $2^{128}$ is "at least several decades if it can be done", rather than a few years. $2^{256}$ is pretty much just "never". Also, why are you talking about integer factorization, when the question was about elliptic curves? – otus May 18 '16 at 14:09
• Well whatever, my point was simply that this is completely impractical currently, I've not done any concrete estimation for this part of the question. Not sure I understand the NSA part too :) Shor's algorithm can be used either for discrete logarithm or for factorization, and the complexity I had in mind was related to the case where it's used for factoring some modulus $n$. For such a question, we're just talking about very rough estimations, so my point was just a comparison between Shor's algorithm and the complexity of matrix multiplication. – Geoffroy Couteau May 18 '16 at 15:11
• It obviously cannot, as you obviously cannot say anything regarding quantum computers - but just stating that is quite useless, right? So I just compared this with a classical algorithm whose complexity is worst than shor's algorithm. Yes, I do not know the constants (and they would not matter as I do not know the time it might take for a quantum computer to execute an operation either), but 2^2048 is huge, so stating it "could be faster than matrix multiplication" on huge inputs is "not so unreasonable". Do you think I could have made a better statement? – Geoffroy Couteau Jun 17 '16 at 17:23
• If matrix multiplication takes few minutes and shor's algorithm "could be faster than matrix multiplication", then how is it a problem to say it "could be less than à few minutes"? (Note that I'm discussing that topic, but fundamentally I agree that the kind of answer I made is very doubtful - I just thought I would be better than no answer at all for tacoma) – Geoffroy Couteau Jun 17 '16 at 19:50