Quadratic residuosity problem

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. (A note on terminology: mathematicians say "residuacity": "residuosity", something of a malapropism, has been adopted by most cryptographers.)

Given the specific case of "N" the product of distinct large prime numbers "p" and "q", the structure of the squaring

:"a" → "a"² 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:

:$frac\{(p\; -\; 1)(q\; -\; 1)\}\{4\}$

If we consider the same mapping modulo "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 quadratic residue symbol takes the value +1 precisely on squares.

In the composite case the corresponding symbol characterises a subgroup of the residues which is too large by factor of two; that is, it rules out roughly half of the residues mod "N", while the problem as posed is to characterise a subset of size a quarter of "N". This difference constitutes the quadratic residuosity problem, in this particular but essential case of "N" having two prime factors.

The working assumption is that bridging this gap, in effective computational terms, is only to be done by lengthy calculation, when quantified in terms of the size of "N".

The Quadratic residuosity problem is the foundation of the Goldwasser-Micali cryptosystem.

ee also

* Higher residuosity problem
* Computational hardness assumptions