Editing Quadratic residue (section)

==Complexity of finding square roots==

That is, given a number ''a'' and a modulus ''n'', how hard is it
# to tell whether an ''x'' solving ''x''<sup>2</sup> ≡ ''a'' (mod ''n'') exists
# assuming one does exist, to calculate it?

An important difference between prime and composite moduli shows up here. Modulo a prime ''p'', a quadratic residue ''a'' has 1 + (''a''|''p'')  roots (i.e. zero if ''a'' N ''p'', one if ''a'' ≡ 0 (mod ''p''), or two if ''a'' R ''p'' and gcd(''a,p'') = 1.)

In general if a composite modulus ''n'' is written as a product of powers of distinct primes, and there are ''n''<sub>1</sub> roots modulo the first one, ''n''<sub>2</sub> mod the second, ..., there will be ''n''<sub>1</sub>''n''<sub>2</sub>... roots modulo ''n''.

The theoretical way solutions modulo the prime powers are combined to make solutions modulo ''n'' is called the [[Chinese remainder theorem]]; it can be implemented with an efficient algorithm.<ref>{{Harvnb|Bach|Shallit|1996|p=104 ff}}; it requires O(log<sup>2</sup> ''m'') steps where ''m'' is the number of primes dividing ''n''.</ref>

<blockquote>For example:
:Solve x<sup>2</sup> ≡ 6 (mod 15).
::x<sup>2</sup> ≡ 6 (mod 3) has one solution, 0; x<sup>2</sup> ≡ 6 (mod 5) has two, 1 and 4.
:: and there are two solutions modulo 15, namely 6 and 9.

:Solve x<sup>2</sup> ≡ 4 (mod 15).
::x<sup>2</sup> ≡ 4 (mod 3) has two solutions, 1 and 2; x<sup>2</sup> ≡ 4 (mod 5) has two, 2 and 3.
:: and there are four solutions modulo 15, namely 2, 7, 8, and 13.
 
:Solve x<sup>2</sup> ≡ 7 (mod 15).
::x<sup>2</sup> ≡ 7 (mod 3) has two solutions, 1 and 2; x<sup>2</sup> ≡ 7 (mod 5) has no solutions.
:: and there are no solutions modulo 15.
</blockquote>

===Prime or prime power modulus===

First off, if the modulus ''n'' is prime the [[Legendre symbol]] <math>\left(\frac{a}{n}\right)</math> can be [[Jacobi symbol#Calculating the Jacobi symbol|quickly computed]] using a variation of [[Euclid's algorithm]]<ref>{{Harvnb|Bach|Shallit|1996|p=113}}; computing <math>\left(\frac{a}{n}\right)</math> requires O(log ''a'' log ''n'') steps</ref> or the [[Euler's criterion]]. If it is −1 there is no solution.
Secondly, assuming that <math>\left(\frac{a}{n}\right)=1</math>, if ''n'' ≡ 3 (mod 4), [[Joseph Louis Lagrange|Lagrange]] found that the solutions are given by
:<math>x \equiv  \pm\; a^{(n+1)/4} \pmod{n},</math>
and [[Adrien-Marie Legendre|Legendre]] found a similar solution<ref>Lemmermeyer, p. 29</ref> if ''n'' ≡ 5 (mod 8):
:<math>x \equiv  \begin{cases}  
\pm\; a^{(n+3)/8}            \pmod{n}& \text{ if } a \text{ is a quartic residue modulo } n \\
\pm\; a^{(n+3)/8}2^{(n-1)/4} \pmod{n}& \text{ if } a \text{ is a quartic non-residue modulo } n \end{cases}</math>

For prime ''n'' ≡ 1 (mod 8), however, there is no known formula. [[Shanks&ndash;Tonelli algorithm|Tonelli]]<ref>{{Harvnb|Bach|Shallit|1996|p=156 ff}}; the algorithm requires O(log<sup>4</sup>''n'') steps.</ref> (in 1891) and [[Cipolla's algorithm|Cipolla]]<ref>{{Harvnb|Bach|Shallit|1996|p=156 ff}}; the algorithm requires O(log<sup>3</sup> ''n'') steps and is also nondeterministic.</ref>  found efficient algorithms that work for all prime moduli. Both algorithms require finding a quadratic nonresidue modulo ''n'', and there is no efficient deterministic algorithm known for doing that. But since half the numbers between 1 and ''n'' are nonresidues, picking numbers ''x'' at random and calculating the Legendre symbol <math>\left(\frac{x}{n}\right)</math> until a nonresidue is found will quickly produce one.  A slight variant of this algorithm is the [[Tonelli–Shanks algorithm]].

If the modulus ''n'' is a [[prime power]] ''n'' = ''p''<sup>''e''</sup>, a solution may be found modulo ''p'' and "lifted" to a solution modulo ''n'' using [[Hensel's lemma]] or an algorithm of Gauss.<ref name="Gauss, DA, art. 101"/>

===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).