Quadratic residuosity problem
 | This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: jargon - this is a simple concept. (November 2010) |
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculation the quadratic residues in modular arithmetic for a modulus N, where N is a composite number. This is an important consideration in contemporary cryptography.[1]
Formulation
Given the specific case of N the product of distinct odd prime numbers p and q, the structure of the squaring map:
- a → a2 modulo N
on the multiplicative group of invertible residues modulo N, is as a group homomorphism with kernel a Klein group of order four. The image is therefore, roughly speaking, of size N/4. More precisely, it is of order:
If we consider the same mapping modulo prime p the kernel is of order 2, the order of the image is (p − 1)/2. In that case it is easy, computationally speaking, to characterise the image, since the Jacobi symbol modulo p takes the value +1 precisely on squares.
Modulo composite N the corresponding Jacobi symbol characterises a subgroup of the residues which is larger by factor of two; that is, it rules out roughly half of the residues modulo N, while the problem as posed is to characterize a subset of size a quarter of N. This difference constitutes the quadratic residuosity problem, in this particular but essential case of N being the product of two primes.
The computational hardness assumption is that bridging this gap can only to be done by lengthy calculation, when quantified in terms of the size of N.
Applications
The quadratic residuosity problem is the foundation of the Goldwasser–Micali cryptosystem.[2][3]
See also
Notes
- ^ Mathematicians say residuacity: residuosity, something of a malapropism, has been adopted by most cryptographers.
- ^ 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.