Algorithme de Tonelli–Shanks

Algorithme déterministe qui calcule une racine carrée d'un résidu quadratique a modulo un nombre premier impair p (trouver x tel que x^2 ≡ a (mod p)) par exponentiation et corrections itératives en utilisant la décomposition p−1 = q·2^s et un non-résidu quadratique.