4
$\begingroup$

It is not easy to understand why this becomes a hard problem.

The discrete logarithm problem as defined here:
“any integer k that solves $b^k = \{g\mod{n}\}$ is termed a discrete logarithm” i.e.:
Finding an integer $k$ for $b$ and $g$ known in $b^k=\{g\mod{n}\}$

I wonder. Is the reverse, that is:
Finding an integer $b$ for $k$ and $g$ known in $b^k=\{g\mod{n}\}$
equally difficult (equivalent), or there are easy ways to solve the later, and if so, how?

Edit: Here is a detailed analysis of “roots”. And here a related answer for n composite.

Edit:
A special case of the discrete logarithm problem is: “Discrete logarithms are perhaps simplest to understand in the group $( \mathbb{Z}_p)^x$. This is the group of multiplication modulo the prime p.”

That was the initial intent of the question. But I realize that a general answer may be more apropiate.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ Here is a related question that deals with computing roots when the modulus is composite. $\endgroup$ – mikeazo Apr 23 '15 at 1:56
  • $\begingroup$ Typically dlog is defined in a group mod p, but it doesn't have to be. I think that other question contains your answer, though not explicitly, so I'd leave this one open. It says "Yes, the problem of finding... is believed hard unless the factorization of $N$ can be determined". Well, you know the factorization of $p$, it is $p$ :) $\endgroup$ – mikeazo Apr 23 '15 at 2:15
  • $\begingroup$ For $k=2$ you use Tonelli-Shanks. $\endgroup$ – mikeazo Apr 23 '15 at 2:22
  • 1
    $\begingroup$ You need the factorisation of $p-1$ (which is the order of the group) not of $p$. Then, $b = g^{k^{-1} \bmod {p-1}}$. This is essentially the RSA problem, except that in RSA, the order of the group is $(p-1)(q-1)$. $\endgroup$ – fkraiem Apr 23 '15 at 2:29
  • 1
    $\begingroup$ @fkraiem It seems to me that there is no reason to need the factorization of (p-1) if n=p (is prime). The Extended Euclidean algorithm is used (provided k and (p-1) are coprime) to find an inverse. It does not seem to require the pre-factorization of (p-1) (N in the algorithm) en.wikipedia.org/wiki/Extended_Euclidean_algorithm. $\endgroup$ – user23728 Apr 23 '15 at 18:23