I am working on a proof that depends on if an adversary can determine if a number is an $nth$ power for some large prime $p$. My intuition tells me that for a sufficiently large value of $n$ this is impossible. However I am unaware of any theorems that state this. Could you point me in the right direction?
Thanks
Here is a simple way to test whether $r$ is an $n$th power modulo $p$.
Given $n,p,r$, compute the least common multiple $s=nt$ of $n$ and $p-1$, then compute $r^t$. $r$ is an $n$th power modulo $p$ if and only if $r^t\equiv1\pmod p$.
Proof. Let $g$ be a primitive root mod $p$. Then $r=g^u$ for some $u$, and $r^t=g^{tu}\equiv1\pmod p$ if and only if $p-1$ divides $tu$, which makes $u$ a multiple of $n$.