I am trying to understand the runtime complexity of the discrete log problem (in the most basic sense).

So, if we have $\langle g \rangle = G$ and are trying to find $g^x = a, a \in G, 0 < x < ord(G)$, why can we not just iterate through all elements of $G$ and find an answer in linear time? Even if we have to compute $g^x$ by repeated multiplication, wouldn't that just be quadratic time?

  • 3
    $\begingroup$ Because normally in computer science "linear time" is in the length of your input, not in their value (eg a DFA works in linear time in the length of its input). $\endgroup$
    – SEJPM
    Commented Feb 20, 2020 at 22:17
  • $\begingroup$ @SEJPM thank you, but could you please post an answer with a small example? $\endgroup$
    – tau
    Commented Feb 20, 2020 at 23:01

1 Answer 1


wouldn't that just be quadratic time?


TLDR: modular arithmetic.

You may have an impression that it should be easy and takes a small number of steps. But the complexity comes from the fact that we use modular. In a normal arithmetic you know for instance that if $a < b$, then $g^a < g^b$ (for N). But in the modular arithmetic there are no such rule.


Let's take $g = 2099$, modulo $M = 2179$ and compare 1787, 39 and 1279, What is greater, $g^{1787}$, $g^{39}$ or $g^{1279}$?

$g^{1787} = 999$

$g^{39} = 1000$

$g^{1279} = 1001$

We see that $g^{1787} < g^{39}$.

Other view on the same numbers. The equation $g^x = 1000$ has solution $x = 39$. Knowing this, can we guess what is solution of the equation $g^x = 999$? Is it close to $39$? No, it is not close. The solution of $g^x = 999$ is $x = 1787$. There is no simple correlation.

That's why in the modular arithmetic to solve an equation like $g^x = 999$ we have to check every number. If $G = \{1, 2, ..., 10 000\}$, we have to check all these numbers. And if $G = \{1, 2, ..., 2^{512}\}$, we have to check all these $2^{512}$ numbers. In the reality some mathematical properties allow us to skip some groups of numbers and thus to reduce needed calculations. Nevertheless, even if the optimization would reduce that to $2^{256}$, still this would be pretty much work to do. The whole computer power on the Earth will not be sufficient to check all relevant numbers in trillions of years.

  • $\begingroup$ exactly the type explanation i was looking for. thank you! $\endgroup$
    – tau
    Commented Feb 21, 2020 at 3:26

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.