QUADRATIC RESIDUE

In mathematics, a number ''q'' is called a 'quadratic residue' modulo ''n'' if there exists an integer ''x'' such that:
:$\{x^2\}equiv\{q\}mbox\{\; (mod\; \}nmbox\{)\}.$
Otherwise, ''q'' is called a 'quadratic non-residue'.
For example, $3^2\; equiv\; 2\; mbox\{\; (mod\; \}7mbox\{)\}$, and thus 2 is a quadratic residue modulo 7.
In effect, a quadratic residue modulo ''n'' is a number that has a square root in modular arithmetic when the modulus is ''n''.
For odd prime moduli, roughly half of the residue classes are quadratic residue, and half are quadratic non-residue. More precisely, for a prime ''p'' > 2, there are
:
of each kind, excluding 0. (Note that for p=2 we have the trivial statement that every number is a quadratic residue since both 0 and 1 are quadratic residues; but in fact the more general statement is true that in finite fields of even characteristic every element is a square.) Quadratic residues occur in a rather random pattern; this has been exploited in applications to acoustics and cryptography.
Though it can be very difficult to extract square roots in modular arithmetic for large moduli, Gauss' theorem of quadratic reciprocity gives a beautiful and elegant algorithm to compute whether or not a given number is a quadratic residue modulo a prime.

Contents

Complexity of finding square roots

Quadratic residues in cryptography

See also

References

External links

Complexity of finding square roots

The problem of finding a square root in modular arithmetic, in other words solving the above for ''x'' given ''q'' and ''n'', can be a difficult problem. For general composite ''n'', the problem is known to be equivalent to integer factorization of ''n'' (an efficient solution to either problem could be used to solve the other efficiently). On the other hand, if we want to know if there is a solution for ''x'' less than some given limit ''c'', this problem is NP-complete (Adleman, Manders 1978); however, this is a fixed-parameter tractable problem, where ''c'' is the parameter.

Quadratic residues in cryptography

The property that finding a square root of a large composit ''n'' is equivalent to factoring has been used for constructing cryptographic schemes: Rabin cryptosystem, Oblivious transfer.
Another property that is often used in cryptography is the following:
If $n$ is a product of odd prime powers and $x\_1$ and $x\_2$ are relatively prime to ''n'' then the product $x\_1\; x\_2$ is a quadratic residue modulo $n$, if and only if either both $x\_1$ and $x\_2$ are quadratic residues or both $x\_1$ and $x\_2$ are quadratic non-residues.

See also

★ congruence of squares

★ distribution of quadratic residues

★ Gauss's lemma

★ law of quadratic reciprocity

★ Legendre symbol

★ Paley graph

★ quadratic residuosity problem

★ Zolotarev's lemma

References

★ Computers and Intractability: A Guide to the Theory of NP-Completeness, Michael R. Garey and David S. Johnson, , , W.H. Freeman, 1979, ISBN 0-7167-1045-5 A7.1: AN1, pg.249.

★ ''NP''-Complete Decision Problems for Binary Quadratics, Kenneth L. Manders, , , Journal of Computer and System Sciences, 1978

External links

★ MathWorld: Quadratic Residue