If $m=p^k$ is a prime power then I know:


$$\exists x\in \mathbb{Z}:x^n\equiv a\bmod p^k\iff a^{\frac{p-1}{\gcd(n,p-1)}}\equiv 1\bmod p^{j}$$
$$\text{ where: }j=\min\left(v\_p(n)+1+[p\mid n][p=2],k\right)$$


Thus if I have the prime factorization of $m$ then by the Chinese remainder theorem I can just verify the above congruence holds for every prime power $p^{v\_p(m)}$. 


However what if I don't know the prime factorization of $m$? 


Is there still a simple way to determine if $x^n\equiv a\bmod m$ is solvable?


What about just the special case when $n=2$ i.e. $x^2\equiv a\bmod m$ with $m$ composite?



Given any $(a,m,n)\in \mathbb{Z}\times\mathbb{N}^2$ with $\gcd(a,m)=1$ is there a quick way to determine if $x^n\equiv a\bmod m$ is solvable?
The Goldwasser-Micali probabilistic cryptosystem is based on exactly this principle. Let $N=pq$ and let $a$ be an integer with $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=-1$, i.e., $a$ is a non-residue mod $p$ and mod $q$. The numbers $N$ and $a$ are public knowledge. In order to encrypt a single bit $\beta$, choose a random number $r$ and send $c=r^2\bmod{N}$ if $\beta=0$ and $c=ar^2\bmod{N}$ if $\beta=1$. It seems to be a hard problem to determine $\beta$ unless you know how to factor $N$, but if you do know $p$ or $q$, then it's easy, just compute $\left(\frac{c}{p}\right)$. According to Wikipedia, G-M is "the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions." See <https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem> for further details.


