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 1


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.

  • 3
    $\begingroup$ "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? $\endgroup$
    – Maarten Bodewes
    Commented May 17, 2016 at 22:59
  • 1
    $\begingroup$ @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? $\endgroup$
    – otus
    Commented May 18, 2016 at 14:09
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 18, 2016 at 15:11
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Jun 17, 2016 at 17:23
  • 1
    $\begingroup$ 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) $\endgroup$ Commented Jun 17, 2016 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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