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

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

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

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

<p>For more details, see <a href="https://crypto.stackexchange.com/q/6518/351">Finding roots in ℤp</a> on Crypto.SE.</p>

CC BY-SA 3.0
2013-07-11T00:00:57.333Z
2013-07-11T00:00:57.333Z
2017-04-13T12:48:17.970Z
D.W.
<p>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?</p>

<nt.number-theory><comp-number-theory>
Complexity of higher order residues
Turbo
# Complexity of higher order residues

(Asked by: username_0 on 2013-07-10)

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?

**Tags:** nt.number-theory, comp-number-theory


---

## 1 answers

### Answer by username_1 on 2013-07-11. Score: 3 | Accepted answer

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)

For more details, see [Finding roots in ℤp](https://crypto.stackexchange.com/q/6518/351) on Crypto.SE.


---

