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.