how is the complexity to solve `$x^a=b(mod p)$` compared with the complexity of solving discrete logarithm

Question

Is it computationally infeasible to solve $x^a\equiv b \pmod p$ as that in discrete logarithm problem to solve $a^x\equiv b \pmod p$, where $p$ is a large prime and $a,b$ are both positive integer below $p-1$

Answer 1

If $a$ is relatively prime to $p-1$, you can solve for $c$ from $ac\equiv 1$ (mod $p-1$) and raise both sides to the power $c$. You obtain $x\equiv x^{ca}\equiv b^c$ (since $x^{p-1}\equiv 1$) (mod $p$).

If $a$ is not relatively prime to $p-1$, the congruence is not always solvable. However, there should be a least $d$ for which $ac\equiv d$ (mod $p-1$) has a solution and raise both sides to the power $c$. Then one has the congruence $x^d\equiv b^c$ (mod $p-1$). In most cases this will be simpler than the original congruence. The congruence has no solution if $b$ is not a $d$-th power modulo $p$. It should be clear that $d$ will be a divisor of $p-1$ (since it can be computed as the gcd of $a$ and $p-1$) and that $b$ will be a $d$-th power if $b^{p-1/d}\equiv 1$ (mod $p-1$).

That is as far as I can help.

Answer 2

There are probabilistic algorithms to solve your equation with complexity polynomial in $\log p$. That means that you can solve such equations in practice. You can find the algorithms in any book on computational/algorithmic number theory. Funnily enough, there is no known deterministic such algorithm even for $a=2$.