This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order n, why is it assumed to be hard to solve? Doesn't hard mean no polynomial algorithm to solve in the context of cryptography?

  • 2
    $\begingroup$ $O(n)$ is polynomial in the order of the group, in general polynomial-time means polynomial in the number of digits thereof, i.e. $O(\log^k(n))$. This is because we can make $n$ rather large easily (a few hundred digits), but making $\log(n)$ large is "much harder". $\endgroup$
    – Thomas
    Commented Jan 12, 2014 at 11:47

2 Answers 2


While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) = O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations).

Therefore, the basic consideration for $n$ should not be the number of group elements, but its logarithm (which is linear to the length of the numbers. In order to avoid the question: This is valid for any numeral system, regardless of its base). So if we have numbers of a group $\mathbb{G}$, we should set $n=\log_2|\mathbb{G}|$, and brute force algorithms require $O(2^n)$ operations.

Short version with less algebra:

Encrypting or signing something uses exponentiation as operation, and there are algorithms with complexity linear to the length of the numbers (in binary representation), and let's call the length $n$. If you want to test all possible values (aka brute force), there are $\approx2^n$ values to test, and this is exponential in the parameter $n$.

  • 5
    $\begingroup$ Would it be possible to "dumb down" this answer a bit for those of us with interest in the topic, but without the mathematical/algorithmic context that seems to assumed in the current answer? $\endgroup$ Commented Jan 13, 2014 at 19:40
  • 5
    $\begingroup$ done, I hope it is understandable $\endgroup$
    – tylo
    Commented Jan 14, 2014 at 10:31

The polynomial vs. exponential complexity notations for algorithms or problems are always expressed in the input size, i.e. the size of a convenient way to express the problem.

For the discrete algorithm problem, you normally would not write the whole group (or even its multiplication table of size $n^2$) as the input, but only some key parameters which allow calculating the group law, as well as the element of which you want to get the logarithm.

Both can be usually expressed in $m = O(\log(n))$ bits for a group of size $n$.

For example, in the "classical" discrete logarithm problem you only need to express the modulus $n+1$ (which has $\log n$ digits), a basis (often one digit, at most $\log n$), and the element (also $\log n$ digits). The result will also be a number with $\log n$ bits.

In an elliptic curve DL problem, you'll note the base field (i.e. its size/modulus – around $\log n$ bits), and the curve equation (i.e. two or three field elements, at most around $\log n$, often smaller), and a base point (two field elements, around $2·\log n$ bits), together with the point of which you need the logarithm. Again, the result will be a number with $\log n$ bits.

And then polynomial means that the problem can be solved in $O(m^k) = O(\log(n)^k)$ time/space/other resources.

PS: Your naive brute force algorithm needs $O(n)$ multiplication (and comparison) steps, but each of them will need at least $O(\log(n))$ time (in average), so your algorithm needs $O(n·\log(n))$ time, not $O(n)$.

And in practical cryptography, you often don't want just some asymptotic high complexity, but want to calculate that it is practically hard, i.e. calculate some lower limits for the actually used parameters.

  • $\begingroup$ I think his algorithm actually needs $\:\: \large O\left(n\cdot \log(n) \cdot \log(\log(n)) \cdot 2^{O(\log^*(n))}\right) \normalsize \:\:$ time. $\hspace{.773 in}$ $\endgroup$
    – user991
    Commented Jan 14, 2014 at 0:20
  • $\begingroup$ you mean $log_2$ most of the time when you write $log$ $\endgroup$ Commented Mar 15, 2016 at 18:22
  • 2
    $\begingroup$ @David天宇Wong $O(\log_a(n))$ and $O(\log_b(n))$ are the same complexity classes for every choice of $a, b > 1$ (because $\log_a(n) = \log_b(n) · \log_a(b)$. Due to this, the base is often omitted in complexity calculations. $\endgroup$ Commented Apr 2, 2016 at 14:51

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.