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:
Otherwise, q is called a quadratic non-residue. For prime moduli, roughly half of the residue classes are of each type. More precisely, for prime p > 2, there are
of each kind, excluding 0. They occur in a rather random pattern; this has been exploited in applications to acoustics.
In effect, a quadratic residue modulo n is a number that has a square root in modular arithmetic when the modulus is n. This concept plays a large part in classical number theory.
Contents |
[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
- congruence of squares
- distribution of quadratic residues
- Gauss's lemma
- law of quadratic reciprocity
- Legendre symbol
- Paley graph
- quadratic residuosity problem
- Zolotarev's lemma
[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.
[edit] External links
 |
This number theory-related article is a stub. You can help Wikipedia by expanding it. |
