Discrete log problem exponential runtime

Question

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?

Answer 1

wouldn't that just be quadratic time?

No.

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.

Example:

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.