Given integers ${\displaystyle a}$  and ${\displaystyle T}$ , ${\displaystyle a}$  is said to be a quadratic residue modulo ${\displaystyle T}$  if there exists an integer ${\displaystyle b}$  such that

${\displaystyle a\equiv b^{2}{\pmod {T}}}$ .

Otherwise we say it is a quadratic non-residue. When ${\displaystyle T=p}$  is a prime, it is customary to use the Legendre symbol:

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}}$ 

This is a multiplicative character which means ${\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1}$  for exactly ${\displaystyle (p-1)/2}$  of the values ${\displaystyle 1,\ldots ,p-1}$ , and it is ${\displaystyle -1}$  for the remaining.

It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm; see Legendre symbol.

Consider now some given ${\displaystyle N=p_{1}p_{2}}$  where ${\displaystyle p_{1}}$  and ${\displaystyle p_{2}}$  are two different unknown primes. A given ${\displaystyle a}$  is a quadratic residue modulo ${\displaystyle N}$  if and only if ${\displaystyle a}$  is a quadratic residue modulo both ${\displaystyle p_{1}}$  and ${\displaystyle p_{2}}$  and ${\displaystyle \gcd(a,N)=1}$ .

Since we don't know ${\displaystyle p_{1}}$  or ${\displaystyle p_{2}}$ , we cannot compute ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$  and ${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$ . However, it is easy to compute their product. This is known as the Jacobi symbol:

${\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)}$ 

This also can be efficiently computed using the law of quadratic reciprocity for Jacobi symbols.

However, ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$  cannot in all cases tell us whether ${\displaystyle a}$  is a quadratic residue modulo ${\displaystyle N}$  or not! More precisely, if ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$  then ${\displaystyle a}$  is necessarily a quadratic non-residue modulo either ${\displaystyle p_{1}}$  or ${\displaystyle p_{2}}$ , in which case we are done. But if ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$  then it is either the case that ${\displaystyle a}$  is a quadratic residue modulo both ${\displaystyle p_{1}}$  and ${\displaystyle p_{2}}$ , or a quadratic non-residue modulo both ${\displaystyle p_{1}}$  and ${\displaystyle p_{2}}$ . We cannot distinguish these cases from knowing just that ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ .

This leads to the precise formulation of the quadratic residue problem:

Problem: Given integers ${\displaystyle a}$  and ${\displaystyle N=p_{1}p_{2}}$ , where ${\displaystyle p_{1}}$  and ${\displaystyle p_{2}}$  are distinct unknown primes, and where ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ , determine whether ${\displaystyle a}$  is a quadratic residue modulo ${\displaystyle N}$  or not.

If ${\displaystyle a}$  is drawn uniformly at random from integers ${\displaystyle 0,\ldots ,N-1}$  such that ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ , is ${\displaystyle a}$  more often a quadratic residue or a quadratic non-residue modulo ${\displaystyle N}$ ?

As mentioned earlier, for exactly half of the choices of ${\displaystyle a\in \{1,\ldots ,p_{1}-1\}}$ , then ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1}$ , and for the rest we have ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1}$ . By extension, this also holds for half the choices of ${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$ . Similarly for ${\displaystyle p_{2}}$ . From basic algebra, it follows that this partitions ${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$  into 4 parts of equal size, depending on the sign of ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$  and ${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$ .

The allowed ${\displaystyle a}$  in the quadratic residue problem given as above constitute exactly those two parts corresponding to the cases ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$  and ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$ . Consequently, exactly half of the possible ${\displaystyle a}$  are quadratic residues and the remaining are not.

The intractability of the quadratic residuosity problem is the basis for the security of the Blum Blum Shub pseudorandom number generator. It also yields the public key Goldwasser–Micali cryptosystem,^[3][4] as well as the identity based Cocks scheme.

• Higher residuosity problem