The quadratic residuosity problem (QRP[1]) in computational number theory is to decide, given integers
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
of unknown factorization is the product of 2 or 3 primes.
is said to be a quadratic residue modulo
is a prime, it is customary to use the Legendre symbol: This is a multiplicative character which means
It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm; see Legendre symbol.
is a quadratic residue modulo
is a quadratic residue modulo both
However, it is easy to compute their product.
This is known as the Jacobi symbol: This also can be efficiently computed using the law of quadratic reciprocity for Jacobi symbols.
is a quadratic residue modulo
is necessarily a quadratic non-residue modulo either
is a quadratic residue modulo both
We cannot distinguish these cases from knowing just that
This leads to the precise formulation of the quadratic residue problem: Problem: Given integers
are distinct unknown primes, and where
is a quadratic residue modulo
is drawn uniformly at random from integers
As mentioned earlier, for exactly half of the choices of
By extension, this also holds for half the choices of
From basic algebra, it follows that this partitions
into 4 parts of equal size, depending on the sign of
in the quadratic residue problem given as above constitute exactly those two parts corresponding to the cases
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.