Editing Quadratic residue (section)

===Cryptography===

The fact that finding a square root of a number modulo a large composite ''n'' is equivalent to factoring (which is widely believed to be a [[Computational hardness assumption|hard problem]]) has been used for constructing [[cryptography|cryptographic schemes]] such as the [[Rabin cryptosystem]] and the [[oblivious transfer]]. The [[quadratic residuosity problem]] is the basis for the [[Goldwasser-Micali cryptosystem]].

The [[discrete logarithm]] is a similar problem that is also used in cryptography.