3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.