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

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}\).