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).
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.
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 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.
^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. doi:10.1109/SFCS.1980.28. ISSN0272-5428.
^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.