Probabilistic algorithm for $a$ that is not a quadratic residue

Question

We have $Z_n$ ($n\in \mathbb N$).
$a\in Z_n$ is a quadratic residue if exists $x\in Z_n$ s.t. $x^2 =a \pmod n$. If there is no such $x$ that make it so $a$ is not a quadratic residue.

There is a effective probabilistic algorithm that calculate $a\in Z_n$ that is not a quadratic residue?

Thank you!!

P.S. if there is a proof for the algorithm I'd like to get it...

Answer 1

Yes. You can assume $n$ is odd: if $a$ is a quadatic nonresidue modulo the largest odd divisor of $n$, then it's also a quadratic nonresidue modulo $n$ itself. (Indeed, if $4$ divides $n$ then you can choose $a=3$.)

When $n$ is odd, just choose $a$ at random (between $2$ and $n-1$). Calculate the Jacobi symbol (the algorithm described there doesn't require factoring $n$). If the result is $-1$, then $a$ is a quadratic nonresidue. If the result is $1$, then we don't know what $a$ is, so just choose a different $a$ at random. The Jacobi symbol returns $-1$ half the time, and calculating it is as lightning-fast as the Euclidean algorithm, so this is a very effective probabilistic algorithm.