Quadratic residuosity problem
The quadratic residuosity problem 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 .
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.
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 .
Since we don't know or , we cannot compute and . Perhaps surprisingly, however, we can easily compute their product! This is known as the Jacobi symbol:
However, can not 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 unknown, different primes, and where , determine whether is a quadratic residue modulo or not.
If is drawn uniformly at random among those integers from which satisfy , is more often a quadratic residue or a quadratic non-residue modulo ?
As earlier mentioned, 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 . Using basic algebra, it is easy to show that this divides into 4 equal parts, 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.
- Adleman, L. (1980). "On Distinguishing Prime Numbers from Composite Numbers". Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science (FOCS), Syracuse, N.Y. pp. 387–408.
- S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing: 365–377. doi:10.1145/800070.802212.
- S. Goldwasser, S. Micali (1984). "Probabilistic encryption". Journal of Computer and System Sciences. 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9.