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. as well as the identity based Cocks scheme. See also Higher residuosity problem References Computational number theory Computational hardness assumptions Theory of cryptography