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 \{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 \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) \]

Ben Lynn blynn@cs.stanford.edu 💡