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 GoldwassserMicali encryption, or Cocks identitybased 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..p2]\).
Say \(k\) is even. Write \(k = 2m\). Then \((g^m)^2 = a\), so \(a\) is a quadratic residue. Exactly half of \([0..p2]\) 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 \((p1)/2\). If \(k\) is odd, say \(k = 2m + 1\), we get
The square of \(g^{(p1)/2}\) is \(g^{p1} = 1\), so \(g^{(p1)/2}\) is \(1\) or \(1\). But \(g\) has order \(p1\) (\(g\) is a generator) thus we must have \(g^{(p1)/2} = 1\).
If \(k\) is even, say \(k = 2m\), then \(a^{(p1)/2} = g^{(p1)m} = 1\).
In other words, we have proved Euler’s Criterion, which states \(a\) is a quadratic residue if and only if \(a^{(p1)/2} = 1\), and \(a\) is a quadratic nonresidue if and only if \(a^{(p1)/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
The symbol can also be written as \((ap)\).
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\)
and for any \(r\) coprime to \(p\)