Editing Quadratic residue (section)

===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"/>