Added to Favorites

Related Searches

Definitions

Nearby Words

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.)## See also

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

- a → a
^{2}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.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday November 26, 2007 at 20:11:21 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday November 26, 2007 at 20:11:21 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.