Let $a\in {\mathbb{Z}}_n$. We say $a$ is a quadratic residue if there exists some $x$ such that $x^2=a$. Otherwise $a$ is a quadratic nonresidue.

Efficiently distinguishing a quadratic residue from a nonresidue modulo $N=pq$ for primes $p,q$ is an open problem. This is exploited by several cryptosystems, such as Goldwassser-Micali encryption, or Cocks identity-based encryption. More general variants of this problem underlie other cryptosystems such as Paillier encryption.

Let $p$ be a prime. From now assume $p>2$, as the case $p=2$ is trivial. Let $g$ be a generator of ${\mathbb{Z}}_p^{*}$. Any $a\in {\mathbb{Z}}_p^{*}$ can be written as $g^k$ for some $k\in \{1,...,p-1\}$.

Say $k$ is even. Write $k=2m$. Then $(g^m{)}^2=a$, so $a$ is a quadratic residue. Exactly half of $\{1,...,p-1\}$ is even (since $p$ is odd), hence at least half of the elements of ${\mathbb{Z}}_p^{*}$ are quadratic residues.

Suppose we have $b^2=a$. Then $(-b{)}^2=a$ as well, and since $b\ne -b$ (since $p>2$) every quadratic residue has at least two square roots (actually we know from studying polynomials there can be at most two), thus at most half the elements of ${\mathbb{Z}}_p^{*}$ are quadratic residues. (Otherwise there are more square roots than elements!)

Thus exactly half of ${\mathbb{Z}}_p^{*}$ are quadratic residues, and they are the even powers of $g$.

Given $a=g^k$, consider the effect of exponentiating by $(p-1)/2$. If $k$ is odd, say $k=2m+1$, we get

The square of $g^{(p-1)/2}$ is $g^{p-1}=1$, so $g^{(p-1)/2}$ is $1$ or $-1$. But $g$ has order $p-1$ ($g$ is a generator) thus we must have $g^{(p-1)/2}=-1$.

If $k$ is even, say $k=2m$, then $a^{(p-1)/2}={g^{(p-1)}}^m=1$.

Thus one way to tell if $a$ is a quadratic residue is to compute $a^{(p-1)/2}$: if the result is $1$, then $a$ is a quadratic residue, otherwise the result is $-1$ and $a$ is a quadratic nonresidue.

Example: In ${\mathbb{Z}}_p$, if $(p-1)/2$ is even (so $p=1(mod4)$), then $-1$ is a quadratic residue, otherwise $-1$ is a quadratic nonresidue.

This fact (sometimes called Euler’s Criterion) is so useful that we define the Legendre symbol for odd primes $p$ and integers $a$ by

The symbol can also be written as $(a\mid p)$.

Thus:

Some basic properties: for any integer $b$

and for any $r$ coprime to $p$