Quadratic residuosity problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number. This is an important consideration in contemporary cryptography.[1]

Formulation[edit]

Given the specific case of N being the product of distinct odd prime numbers p and q, the structure of the squaring map:

aa2 mod 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 of size roughly N/4. More precisely, it is of order:

\frac{(p - 1)(q - 1)}{4}

In contrast, the same mapping modulo prime P has the kernel of order 2 and the image of order (P − 1)/2. In this case it is easy to characterize the image computationally, since the Jacobi symbol takes the value +1 precisely on quadratic residues modulo P.

Modulo composite N the corresponding Jacobi symbol characterizes 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[edit]

The intractability of the quadratic residuosity problem is the basis for the security of the Blum Blum Shub pseudo-random number generator and the Goldwasser–Micali cryptosystem.[2][3]

See also[edit]

Notes[edit]

  1. ^ Mathematicians say residuacity: residuosity, something of a malapropism, has been adopted by most cryptographers.
  2. ^ 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. 
  3. ^ 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.