Determining if a number is an nth root 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$. 
