Quadratic Residues

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 an odd prime, as the case $p=2$ is trivial. Let $g$ be a generator of ${\mathbb{Z}}_p^{\ast }$. Any $a\in {\mathbb{Z}}_p^{\ast }$ can be written as $g^k$ for some $k\in [0..p-2]$.

Say $k$ is even. Write $k=2m$. Then $(g^m{)}^2=a$, so $a$ is a quadratic residue. Exactly half of $[0..p-2]$ is even (since $p$ is odd), hence at least half of the elements of ${\mathbb{Z}}_p^{\ast }$ 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 (in fact, we know from studying polynomials there can be at most two), thus at most half the elements of ${\mathbb{Z}}_p^{\ast }$ are quadratic residues. (Otherwise there are more square roots than elements!)

Thus exactly half of ${\mathbb{Z}}_p^{\ast }$ 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$.

In other words, we have proved Euler’s Criterion, which states $a$ is a quadratic residue if and only if $a^{(p-1)/2}=1$, and $a$ is a quadratic nonresidue if and only if $a^{(p-1)/2}=-1$.

Example: We have $-1$ is a quadratic residue in ${\mathbb{Z}}_p$ if and only if $p=1(\mathrm{mod}4)$.