# Complexity of higher order residues

Let $P$ be a prime. Given a number $a$, what is the computational complexity in establishing if $a$ is a cubic or higher order residue modulo $P$? Are there any good algorithms?

Yes, there are good (efficient) algorithms. This is completely solved, and the algorithms are widely used in the cryptographic community.

If $\gcd(n,p-1)=1$, then everything is a $n$th residue.

If $n$ divides $p-1$, then $a$ is a $n$th residue if and only if $a^{(p-1)/n} \equiv 1 \pmod p$.

If $1<\gcd(n,p-1)<n$, $a$ is a $n$th residue if and only if it is a $\gcd(n,p-1)$-th residue (see previous case).

For more details, see Finding roots in ℤp on Crypto.SE.