Tonelli–Shanks Algorithm
- Mathematics & Logic -
Pure Mathematics Dictionary
Definition
Deterministic algorithm to compute a square root of a given quadratic residue a modulo an odd prime p (find x with x^2 ≡ a (mod p)) by exponentiation and iterative adjustments using the factorization p−1 = q·2^s and a quadratic nonresidue.