Quadratic residuosity problem

The quadratic residuosity problem (QRP^[1]) in computational number theory is to decide, given integers ${\displaystyle a}$ and ${\displaystyle N}$, whether ${\displaystyle a}$ is a quadratic residue modulo ${\displaystyle N}$ or not. Here ${\displaystyle N=p_{1}p_{2}}$ for two unknown primes ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$, and ${\displaystyle a}$ is among the numbers which are not obviously quadratic non-residues (see below).

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.^[2]