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

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$

-

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.

-

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$.

-
For $a=2$ there's Schoof's algorithm. It's polynomial time. I had thought it was deterministic, but I may be misremembering. – Joe Silverman Jan 29 '11 at 14:59
@Joe: as far as I know it is deterministic. – GH from MO Jan 29 '11 at 15:18
Schoof's algorithm is deterministic but requires an elliptic curve with CM by a field with discriminant $\pm b$ so the running time is proportional to $b$ (but polynomial in $\log p$) so is only really polynomial time for fixed $b$. – Felipe Voloch Jan 29 '11 at 18:50
Being pedantic: proportional to $\sqrt{|b|}$, and polynomial time for $b=O(log^C(p))$, $C$ a constant. – Dror Speiser Jan 29 '11 at 23:25
Also, note that if $a$ isn't fixed and grows with $p$, say, more than polynomially, this is an open problem. – Dror Speiser Jan 29 '11 at 23:27