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 example, , 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. 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 an algorithm to compute whether or not a given number is a quadratic residue modulo a prime.

Every number is a quadratic residue modulo p=2; thus the restriction to odd primes above is necessary.

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.

The property that finding a square root of a large composite 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 an odd prime power and x₁ and x₂ are relatively prime to n then the product x₁x₂ is a quadratic residue modulo n, if and only if either both x₁ and x₂ are quadratic residues or both x₁ and x₂ are quadratic non-residues.

• congruence of squares
• distribution of quadratic residues
• Gauss's lemma
• law of quadratic reciprocity
• Legendre symbol
• Paley graph
• quadratic residuosity problem
• Zolotarev's lemma

• 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. 

• MathWorld: Quadratic Residue