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 = p q$ 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 \gt 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 \gt 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

\[ a^{(p-1)/2} = g^{(2m+1)(p-1)/2} = {g^{(p-1)}}^m g^{(p-1)/2} = g^{(p-1)/2} \]

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 \pmod {4}$), then $-1$ is a quadratic residue, otherwise $-1$ is a quadratic nonresidue.

The Legendre Symbol

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

\[ \left(\frac{a}{p}\right) = a^{(p-1)/2} . \]

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

Thus:

  • $\left(\frac{a}{p}\right) = 1$ if $a$ is a quadratic residue of $p$

  • $\left(\frac{a}{p}\right) = -1$ if $a$ is a quadratic nonresidue of $p$

  • $\left(\frac{a}{p}\right) = 0$ if $a = 0$ modulo $p$

Some basic properties: for any integer $b$

\[ \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = \left(\frac{a b}{p}\right) \]

and for any $r$ coprime to $p$

\[ \left(\frac{a}{p}\right)\left(\frac{a r^2}{p}\right) = \left(\frac{a}{p}\right) \]