Quadratic residue
Encyclopedia : Q : QU : QUA : Quadratic residue
In mathematics, a number q is called a quadratic residue modulo n if there exists an integer x such that:
- [\equiv\mboxn\mbox.]
- (p − 1)/2
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.
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.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
- A7.1: AN1, pg.249.
External links
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.