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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
