information:extraction, linguistic:paraphrasing, information:highlighting, structural:reformatting
Prime or prime power modulus

First off, if the modulus n is prime the Legendre symbol (a n) {\displaystyle \left({\frac {a}{n}}\right)} can be quickly computed using a variation of Euclid's algorithm or the Euler's criterion. If it is −1 there is no solution.Secondly, assuming that (a n) = 1 {\displaystyle \left({\frac {a}{n}}\right)=1}, if n ≡ 3 (mod 4), Lagrange found that the solutions are given by

and Legendre found a similar solution if n ≡ 5 (mod 8):

For prime n ≡ 1 (mod 8), however, there is no known formula. Tonelli (in 1891) and Cipolla 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 (x n) {\displaystyle \left({\frac {x}{n}}\right)} 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, a solution may be found modulo p and "lifted" to a solution modulo n using Hensel's lemma or an algorithm of Gauss.