# Discrete log problem exponential runtime

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?

• 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). Feb 20, 2020 at 22:17
• @SEJPM thank you, but could you please post an answer with a small example?
– tau
Feb 20, 2020 at 23:01

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.

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