I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer..

If $h=g^x \bmod p$ and we're working in the group $Z^*_p$, why can I not find $x$ in linear time given I have $h, g, p$, and $Z^*_p$? I have at most $\operatorname{ord}(Z^*_p)$ iterations to run through?

I can't see what aspect of the maths I'm obviously misunderstanding. Is it not linear to calculate $g^x \bmod p$ for some $x$? That's my only guess.

  • $\begingroup$ Linear doesn't mean computationally feasible. Try a loop from 1 to $2^{128}$ just for counting the steps. $\endgroup$
    – kelalaka
    May 7 '19 at 18:59
  • $\begingroup$ @kelalaka But this problem is definitely NP, not a polynomial class of problem. I know that is the case, so it must not be linear, but I don't know why. $\endgroup$ May 7 '19 at 19:03
  • $\begingroup$ $\lvert(\mathbb Z/p)^\ast\rvert$ is exponential in $\log p$. (It is "linear", but... in what?) $\endgroup$
    – yyyyyyy
    May 7 '19 at 19:08
  • $\begingroup$ When computing complexity classes, we look at the effort required for the particular problem size; for a problem of the form $h = g^x \bmod p$, we can express $h$ (and $g$ and $p$) in binary; and so as a function of problem size (the size of $h$ in binary), the effort required for a linear scan is exponential... $\endgroup$
    – poncho
    May 7 '19 at 20:40

It is true that you have in the worst case $\operatorname{ord}(Z^*_p)$ values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary. Here the inputs to our problem are h and p. These two are integers both of size $log_2(p)$ at most in computer binary representation. And the algorithm would take $\operatorname{ord}(Z^*_p) = p$ iterations. However, $p = 2^{log_2(p)}$, so we can clearly see that the number of iterations required is actually exponential to the size of our input of the problem. Which is why the discret logarithm problem is hard.
When you usually see complexities of the form $O(n)$ or $O(log(n))$, we actually assume that the size of our problem is $n$ in computer representation, without explicitely saying it.


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.