Quadratic residue

From Wikipedia, the free encyclopedia

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 }n\mbox{)}.$

Otherwise, q is called a quadratic non-residue. For example, $3^2 \equiv 2 \mbox{ (mod }7\mbox{)}$ , 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 of each type. More precisely, for prime p > 2, there are

$\frac{p-1}{2}$

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.

1 Complexity of finding square roots
2 See also
3 References
4 External links

[edit] 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.

[edit] See also

[edit] References

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A7.1: AN1, pg.249.
Kenneth L. Manders; Leonard Adleman (1978). "NP-Complete Decision Problems for Binary Quadratics". Journal of Computer and System Sciences 16 (2): 168–184. DOI:10.1016/0022-0000(78)90044-2.