0
$\begingroup$

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?

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

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ exactly the type explanation i was looking for. thank you! $\endgroup$ – tau Feb 21 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.