The quadratic residuosity problem (QRP[1]) in computational number theory is to decide, given integers and , whether is a quadratic residue modulo or not.Here for two unknown primes and , and 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.[2]
Precise formulation
Given integers and
,
is said to be a quadratic residue modulo
if there exists an integer
such that
.
Otherwise we say it is a quadratic non-residue.When is a prime, it is customary to use the Legendre symbol:
This is a multiplicative character which means for exactly
of the values
, and it is
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 where
and
are two different unknown primes.A given
is a quadratic residue modulo
if and only if
is a quadratic residue modulo both
and
and
.
Since we don't know or
, we cannot compute
and
. 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.
However, cannot in all cases tell us whether
is a quadratic residue modulo
or not!More precisely, if
then
is necessarily a quadratic non-residue modulo either
or
, in which case we are done.But if
then it is either the case that
is a quadratic residue modulo both
and
, or a quadratic non-residue modulo both
and
.We cannot distinguish these cases from knowing just that
.
This leads to the precise formulation of the quadratic residue problem:
Problem:Given integers and
, where
and
are distinct unknown primes, and where
, determine whether
is a quadratic residue modulo
or not.
Distribution of residues
If is drawn uniformly at random from integers
such that
, is
more often a quadratic residue or a quadratic non-residue modulo
?
As mentioned earlier, for exactly half of the choices of , then
, and for the rest we have
.By extension, this also holds for half the choices of
.Similarly for
.From basic algebra, it follows that this partitions
into 4 parts of equal size, depending on the sign of
and
.
The allowed in the quadratic residue problem given as above constitute exactly those two parts corresponding to the cases
and
.Consequently, exactly half of the possible
are quadratic residues and the remaining are not.
Applications
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.