Is there an efficient way (algorihtm) to compute the solutions of the congruence $x^n\equiv a \mod p$$x^n\equiv a \pmod p$?
$n\in \mathbb{N}$
$a\in\mathbb{Z}_p$
p$p$ is a large prime number
Note that:
By efficient I mean computationally efficient even when the given prime $p$ is appropriate for use in cryptographic protocols (hard to find discrete logarithm in $\mathbb{Z_p}$$\mathbb{Z}_p$)
We do not know the prime factors of $p-1$.
It’s easy to find one solution when gcd(n,p-1)=1$\gcd(n,p-1)=1$.
I think this should be as hard as finding a Discrete Logarithm or as Factoring. Any ideas ? Thank you for your time.
