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 formula_32 until a nonresidue is found will quickly produce one. A slight variant of this algorithm is the Tonelli–Shanks algorithm.