Quadratic residuosity problem

The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult. Several cryptographic methods rely on its hardness, see § Applications.

An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite ${\displaystyle N}$ of unknown factorization is the product of 2 or 3 primes.

Precise formulation

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(\mathrm{mod}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{array}{ll}1& \text{ if }a\text{ is a quadratic residue modulo }p\text{ and }a\not\equiv 0(\mathrm{mod}p),\\ -1& \text{ if }a\text{ is a quadratic non-residue modulo }p,\\ 0& \text{ if }a\equiv 0(\mathrm{mod}p).\end{array}}$

This is a multiplicative character which means ${\displaystyle (\frac{a}{p})=1}$ for exactly ${\displaystyle (p-1)/2}$ of the values ${\displaystyle 1,\dots ,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 (\frac{a}{p_1})}$ and ${\displaystyle (\frac{a}{p_2})}$. 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 (\frac{a}{N})}$ cannot in all cases tell us whether ${\displaystyle a}$ is a quadratic residue modulo ${\displaystyle N}$ or not! More precisely, if ${\displaystyle (\frac{a}{N})=-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 (\frac{a}{N})=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 (\frac{a}{N})=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 (\frac{a}{N})=1}$, determine whether ${\displaystyle a}$ is a quadratic residue modulo ${\displaystyle N}$ or not.