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 an odd prime, 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 [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^*$$ 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^*$$ 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$$.

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 \pmod {4}$$.

## The Legendre Symbol

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$$

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 r^2}{p}\right) = \left(\frac{a}{p}\right)$

Ben Lynn blynn@cs.stanford.edu 💡