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.

Principe

Ramener la recherche de racine à des exponentiations répétées et des corrections multiplicatives contrôlées : écrire p−1 = q·2^s avec q impair, choisir un non-résidu quadratique z, former un candidat initial a^{(q+1)/2}, puis corriger itérativement au moyen de puissances de z pour éliminer les obstructions 2-adiques jusqu'à obtenir une racine carrée effective.

Démonstration

Exemple : pour p = 11 et a = 3, l'algorithme vérifie que 3 est un résidu quadratique, choisit un non-résidu z (par exemple z = 2), écrit p−1 = 10 = 5·2^1, calcule le candidat initial a^{(q+1)/2} = 3^{3} ≡ 5 (mod 11) et constate que 5^2 ≡ 3, donc x = 5 (et 6) sont des racines ; la même suite d'exponentiations et de corrections s'applique pour des p plus grands.

Mauvaise application

Appliquer l'algorithme tel quel pour un module composite n ou pour p = 2, ou l'utiliser lorsque a n'est pas un résidu quadratique conduit à l'échec ; omettre la décomposition 2-adique p−1 = q·2^s ou prendre z qui est en réalité un résidu donne des résultats erronés.

Conséquence

Bien appliqué, il fournit une racine carrée modulo un premier impair et constitue une méthode déterministe et pratique employée dans des routines arithmétiques modulaires (par exemple la décompression de points sur courbes elliptiques ou les algorithmes nécessitant des racines modulaires).

Inversion

La perspective inverse consiste à partir d'un candidat x et à tester x^2 mod p pour certifier a ; alternativement, l'impossibilité de produire une racine permet, via le symbole de Legendre, d'attester l'absence de racine. En contraste, pour des premiers p ≡ 3 (mod 4) on peut utiliser directement x = a^{(p+1)/4} sans les itérations Tonelli–Shanks.

Limite

Ne s'applique qu'aux modules premiers impairs p et aux entrées a qui sont des résidus quadratiques modulo p ; il n'est pas valable pour des modules composites sans modification et exige l'existence d'un non-résidu quadratique modulo p pour effectuer les corrections.

Tension sémantique

Conflit d'usages avec d'autres méthodes de racine carrée modulaire comme l'algorithme de Cipolla (qui utilise une extension quadratique du corps) ou les raccourcis d'exponentiation pour premiers particuliers ; les compromis portent sur le caractère déterministe, les constantes et la facilité d'implémentation.

Synthèse

Tonelli–Shanks est une méthode déterministe structurée qui transforme le problème de racine carrée modulaire en une suite contrôlée d'exponentiations et de corrections multiplicatives fondées sur la décomposition 2-adique de p−1 et un non-résidu choisi, produisant une racine réelle lorsque celle-ci existe.