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

In other words, \(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

The above 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 💡