Editing Quadratic residue (section)

===Composite modulus===

If the modulus ''n'' has been factored into prime powers the solution was discussed above.

If ''n'' is not congruent to 2 modulo 4 and the [[Kronecker symbol]] <math>\left(\tfrac{a}{n}\right)=-1</math> then there is no solution; if ''n'' is congruent to 2 modulo 4 and <math>\left(\tfrac{a}{n/2}\right)=-1</math>, then there is also no solution. If ''n'' is not congruent to 2 modulo 4 and <math>\left(\tfrac{a}{n}\right)=1</math>, or ''n'' is congruent to 2 modulo 4 and <math>\left(\tfrac{a}{n/2}\right)=1</math>, there may or may not be one.

If the complete factorization of ''n'' is not known, and <math>\left(\tfrac{a}{n}\right)=1</math> and ''n'' is not congruent to 2 modulo 4, or ''n'' is congruent to 2 modulo 4 and <math>\left(\tfrac{a}{n/2}\right)=1</math>, the problem is known to be equivalent to [[integer factorization]] of ''n'' (i.e. an efficient solution to either problem could be used to solve the other efficiently).
<blockquote>The above discussion indicates how knowing the factors of ''n'' allows us to find the roots efficiently. Say there were an efficient algorithm for finding square roots modulo a composite number. The article [[congruence of squares]] discusses how finding two numbers x and y where {{math|''x''<sup>2</sup> ≡ ''y''<sup>2</sup> (mod ''n'')}} and {{math|''x'' &ne; ±''y''}} suffices to factorize ''n'' efficiently. Generate a random number, square it modulo ''n'', and have the efficient square root algorithm find a root. Repeat until it returns a number not equal to the one we originally squared (or its negative modulo ''n''), then follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.<ref>Crandall & Pomerance, ex. 6.5 & 6.6, p.273</ref></blockquote>

Determining whether ''a'' is a quadratic residue or nonresidue modulo ''n'' (denoted {{math|''a'' R ''n''}} or {{math|''a'' N ''n''}}) can be done efficiently for prime ''n'' by computing the Legendre symbol. However, for composite ''n'', this forms the [[quadratic residuosity problem]], which is not known to be as [[Computational hardness assumption|hard]] as factorization, but is assumed to be quite hard.

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]];<ref>{{harvnb|Manders|Adleman|1978}}</ref> however, this is a [[fixed-parameter tractable]] problem, where ''c'' is the parameter.

In general, to determine if ''a'' is a quadratic residue modulo composite ''n'', one can use the following theorem:<ref>{{cite book|last=Burton|first=David|title=Elementary Number Theory|year=2007|publisher=McGraw HIll|location=New York|pages=195}}</ref>

Let {{math|''n'' > 1}}, and {{math|1=gcd(''a'',''n'') = 1}}. Then {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}} is solvable if and only if:

* The [[Legendre symbol]] <math>\left(\tfrac{a}{p}\right)=1</math> for all odd prime divisors ''p'' of ''n''.
* {{math|''a'' ≡ 1 (mod 4)}} if ''n'' is divisible by 4 but not 8; or {{math|''a'' ≡ 1 (mod 8)}} if ''n'' is divisible by 8.

Note: This theorem essentially requires that the factorization of ''n'' is known.  Also notice that if {{math|1=gcd(''a'',''n'') = ''m''}}, then the congruence can be reduced to {{math|''a''/''m'' ≡ ''x''<sup>2</sup>/''m'' (mod ''n''/''m'')}}, but then this takes the problem away from quadratic residues (unless ''m'' is a square).