system
Given the following post, respond as if you're commenting on Reddit:
human
Is an O(sqrt(n)) solution really that bad?

So I am researching elliptic curve cryptography and I keep getting terribly confused about what I'm reading.  Let me give some very basic background:


BACKGROUND:  Many traditional cryptosystems are built so that to "break" the system, one has to be able to solve a problem called the "Discrete Logarithm Problem"  Conversely, to break an ECC system, one has to be able to solve the "Elliptic Curve Discrete Logarithm Problem."  One of the reasons ECC is useful, according to every book I read, is because there are subexponential algorithms which solve the regular Discrete Logarithm Problem, but the best current algorithm to solve the ECDLP runs in O(sqrt(n)) - this is supposedly indicating the ECC system is harder to break. 


 Every single book I read seems to say this but this is really confusing me.  What's so bad about an O(sqrt(n)) time solution?  I guess I'm confused because back in my original programming class, a lot of the search algorithms and just regular algorithms we learned would be O(n^2).  I remember how an O(n) linear solution always seemed like a great solution.  Isn't O(sqrt(n)) even better?  Also, how is O(sqrt(n)) NOT a subexponential solution?


Example quote from book: Elliptic Curves in Cryptography by Blake, p.80: (talking about algorithms to "break" ECC systems): "The last two attacks listed are quite general  but have complexities on the order of sqrt(n).  They become infeasible when the curve order is sufficiently large."  


another quote:
"The main reason why (ECC) is "more trusted".... is because (the discrete logarithm problem)... can be solved in subexponential time with index calculus algorithms. Until recently... the time required to solve (an ECC system) was believed to be exponential in the size of the parameters."
gpt
The search algorithms are parameterized in terms of input length.  The n is very likely a number and not the size of a number.  The input length is then log(n).  So if an algorithm takes O(sqrt(n)) time it will take O(2^{k/2}) if k is the bit length of n.