Algorithme de Tonelli-Shanks

Soit ${\displaystyle p}$ un nombre premier impair. On convient d'écrire des égalités à la place de congruences modulo ${\displaystyle p}$.

Étant donné un entier non nul ${\displaystyle n}$, le critère d'Euler exprime que ${\displaystyle n}$ a une racine carrée modulo ${\displaystyle p}$ (c'est-à-dire, ${\displaystyle n}$ est un résidu quadratique) si et seulement si

${\displaystyle n^{\frac {p-1}{2}}=1{\bmod {p}}}$.

À l'opposé, un nombre ${\displaystyle z}$ n'a pas de racine carrée (n'est pas un résidu) si et seulement si

${\displaystyle z^{\frac {p-1}{2}}=-1{\bmod {p}}}$.

Il n'est pas difficile de trouver de tels ${\displaystyle z}$, parce que la moitié des entiers compris entre 1 et ${\displaystyle p-1}$ n'ont pas de racine. Supposons donc savoir calculer un tel ${\displaystyle z}$ qui n'a pas de racine.

En divisant par ${\displaystyle 2}$ de manière répétée, on écrit ${\displaystyle p-1}$ sous la forme ${\displaystyle Q2^{S}}$, où ${\displaystyle Q}$ est impair. En posant

${\displaystyle R=n^{\frac {Q+1}{2}}{\bmod {p}}}$,

on a alors

${\displaystyle R^{2}=n^{Q+1}=n\cdot n^{Q}{\bmod {p}}}$.

Soit ${\displaystyle t=n^{Q}{\bmod {p}}}$. Si jamais on a ${\displaystyle t=1{\bmod {p}}}$, alors ${\displaystyle R}$ est une racine carrée de ${\displaystyle n}$. Sinon, en posant ${\displaystyle M=S}$, on dispose de ${\displaystyle R}$ et ${\displaystyle t}$ tels que

• ${\displaystyle R^{2}\equiv nt{\bmod {p}}}$ et
• ${\displaystyle t}$ est une racine ${\displaystyle 2^{M-1}}$-ième de ${\displaystyle 1}$ (car ${\displaystyle t^{2^{M-1}}=t^{2^{S-1}}=n^{Q2^{S-1}}=n^{(p-1)/2}}$).

Si, disposant de ${\displaystyle R}$ et ${\displaystyle t}$ pour un ${\displaystyle M}$ donné, qui satisfont aux conditions précédentes (où ${\displaystyle R}$ n'est pas une racine carrée de ${\displaystyle n}$), on va trouver d'autres ${\displaystyle R}$ et ${\displaystyle t}$ qui conviennent pour ${\displaystyle M-1}$, et recommencer jusqu'à ce que ${\displaystyle t}$ devienne une racine ${\displaystyle 2^{0}}$-ième de ${\displaystyle 1}$, i.e., ${\displaystyle t=1}$. À ce stade, ${\displaystyle R}$ est une racine carrée de ${\displaystyle n}$.

Pour ce faire, on peut tester si ${\displaystyle t}$ est une racine ${\displaystyle 2^{M-2}}$-ième de l'unité en l'élevant ${\displaystyle M-2}$ fois au carré et en regardant si on trouve 1. Si tel est le cas, il n'y a rien à faire, puisque ces choix de ${\displaystyle R}$ et ${\displaystyle t}$ fonctionnent. Sinon, c'est que ${\displaystyle t^{2^{M-2}}}$ vaut ${\displaystyle -1}$ (puisque son carré vaut 1 et qu'il n'y a que deux racines carrées de 1 modulo ${\displaystyle p}$).

Pour trouver de nouveaux ${\displaystyle R}$ et ${\displaystyle t}$, on cherche à multiplier ${\displaystyle R}$ par un facteur ${\displaystyle b}$ à déterminer. Alors ${\displaystyle t}$ doit être multiplié par le facteur ${\displaystyle b^{2}}$ pour assurer que ${\displaystyle R^{2}=nt}$. Ainsi, quand ${\displaystyle t^{2^{M-2}}=-1}$, on cherche un facteur ${\displaystyle b^{2}}$ tel que ${\displaystyle tb^{2}}$ est une racine ${\displaystyle 2^{M-2}}$-ième de 1 ou, ce qui revient au même, ${\displaystyle b^{2}}$ est lui-même une racine ${\displaystyle 2^{M-2}}$-ième de ${\displaystyle -1}$.

L'astuce consiste à utiliser ${\displaystyle z}$, dont on sait qu'il n'a pas de racine carrée. Le critère d'Euler montre que ${\displaystyle z^{Q}}$ est une racine ${\displaystyle 2^{S-1}}$-ième de ${\displaystyle -1}$ (car ${\displaystyle (z^{Q})^{2^{S-1}}=z^{Q2^{S-1}}=z^{(p-1)/2}=-1}$). En élevant ${\displaystyle z^{Q}}$ au carré de façon répétée, on obtient une suite de racines ${\displaystyle 2^{i}}$-èmes de ${\displaystyle -1}$. On en choisit une pour servir de ${\displaystyle b}$. Avec un peu de soin sur le traitement des variables et une intégration des cas triviaux, on aboutit à l'algorithme suivant.

Dans la suite, les opérations et comparaisons portant sur les éléments se déroulent toutes dans le corps ${\displaystyle \mathbf {F} _{p}=\mathbf {Z} /p\mathbf {Z} }$ des entiers modulo ${\displaystyle p}$.

Entrée :

• ${\displaystyle p}$ un nombre premier impair ;
• ${\displaystyle n}$, un élément de ${\displaystyle \mathbf {F} _{p}}$ pour lequel l'équation ${\displaystyle x^{2}=n}$ admet des solutions ; on dit alors que ${\displaystyle n}$ est un résidu quadratique modulo ${\displaystyle p}$.

Sortie :

• ${\displaystyle r}$ dans ${\displaystyle \mathbf {F} _{p}}$ tel que ${\displaystyle r^{2}=n}$.

Algorithme :

1. En divisant de façon répétée par 2, trouver Q et S tels que ${\displaystyle p-1=Q2^{S}}$ et ${\displaystyle Q}$ est impair.
2. Rechercher un élément ${\displaystyle z}$ dans ${\displaystyle \mathbf {F} _{p}}$ qui n'est pas un résidu quadratique :
   • on tire ${\displaystyle z}$ au hasard et on teste ce candidat à l'aide du critère d'Euler ou en calculant le symbole de Jacobi ;
   • comme la moitié des éléments de ${\displaystyle \mathbf {F} _{p}^{\times }}$ne sont pas des résidus quadratiques, on s'attend à faire deux essais en moyenne.
3. Initialisation :

   ${\displaystyle {\begin{aligned}M&\leftarrow S\\c&\leftarrow z^{Q}\\t&\leftarrow n^{Q}\\R&\leftarrow n^{\frac {Q+1}{2}}.\end{aligned}}}$

4. Boucle :
   • si ${\displaystyle t=0}$, renvoyer ${\displaystyle r=0}$ ;
   • si ${\displaystyle t=1}$, renvoyer ${\displaystyle r=R}$ ;
   • sinon, élever au carré de manière répétée pour trouver le plus petit ${\displaystyle i}$ compris entre ${\displaystyle 1}$ et ${\displaystyle M-1}$ tel que ${\displaystyle t^{2^{i}}=1}$ ;
   • poser ${\displaystyle b\leftarrow c^{2^{M-i-1}}}$, puis

     ${\displaystyle {\begin{aligned}M&\leftarrow i\\c&\leftarrow b^{2}\\t&\leftarrow tb^{2}\\R&\leftarrow Rb.\end{aligned}}}$

Quand on a une solution ${\displaystyle r}$, l'autre est ${\displaystyle -r}$. Si le plus petit exposant ${\displaystyle i}$ tel que ${\displaystyle t^{2^{i}}=1}$ vaut ${\displaystyle M}$, alors il n'existe aucune solution à la congruence, c'est-à-dire que n n'est pas un résidu quadratique.

L'algorithme est particulièrement utile lorsque ${\displaystyle p\equiv 1{\bmod {4}}}$ (notamment pour trouver des racines carrées de ${\displaystyle -1}$). En effet, pour les nombres premiers tels que ${\displaystyle p\equiv 3{\bmod {4}}}$, les racines carrées de ${\displaystyle n}$, si elles existent, sont ${\displaystyle \pm n^{(p+1)/4}{\bmod {p}}}$. Dans ce cas, il est plus efficace de calculer l'une de ces deux valeurs, disons ${\displaystyle r=n^{(p+1)/4}}$, et de vérifier si ${\displaystyle r^{2}=n}$. Si c'est le cas, ${\displaystyle r}$ et ${\displaystyle -r}$ sont les seules solutions. Sinon, ${\displaystyle r^{2}=-n}$ et ${\displaystyle n}$ n'est pas un résidu quadratique, c'est-à-dire qu'il n'y a pas de solutions.

On démontre qu'au début de chaque passage dans la boucle, on a les invariants de boucle suivants :

• ${\displaystyle c^{2^{M-1}}=-1}$ ;
• ${\displaystyle t^{2^{M-1}}=1}$ ;
• ${\displaystyle R^{2}=tn}$.

En effet, au premier passage, on a :

• ${\displaystyle c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1}$ (puisque ${\displaystyle z}$ n'est pas un résidu quadratique) ;
• ${\displaystyle t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1}$ (puisque ${\displaystyle n}$ est un résidu quadratique) ;
• ${\displaystyle R^{2}=n^{Q+1}=tn}$.

À chaque itération, en notant ${\displaystyle M',c',t',R'}$ les nouvelles valeurs des variables ${\displaystyle M,c,t,R}$, on a :

• ${\displaystyle c'^{2^{M'-1}}=(b^{2})^{2^{i-1}}=c^{2^{M-i}2^{i-1}}=c^{2^{M-1}}=-1}$ ;
• ${\displaystyle t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=(-1)\times (-1)=1}$ car :
  • ${\displaystyle t^{2^{i-1}}=-1}$ puisque ${\displaystyle t^{2^{i}}=1}$ but ${\displaystyle t^{2^{i-1}}\neq 1}$ (${\displaystyle i}$ est la plus petite valeur pour laquelle ${\displaystyle t^{2^{i}}=1}$) ;
  • ${\displaystyle b^{2^{i}}=c^{2^{M-i-1}2^{i}}=c^{2^{M-1}}=-1}$ ;
• ${\displaystyle R'^{2}=R^{2}b^{2}=tnb^{2}=t'n}$.

Du fait que ${\displaystyle t^{2^{M-1}}=1}$ et que l'on teste si ${\displaystyle t=1}$ au début de la boucle, on peut toujours trouve un ${\displaystyle i\in \{1,\dots ,M-1\}}$ tel que ${\displaystyle t^{2^{i}}=1}$. À chaque itération, la valeur de ${\displaystyle M}$ décroît strictement, ce qui assure que l'algorithme s'arrête. Lorsque la condition ${\displaystyle t=1}$ est remplie et que l'algorithme s'arrête, le dernier invariant de boucle implique que ${\displaystyle R^{2}=n}$.

Résolvons l'équation ${\displaystyle r^{2}=5{\bmod {4}}1}$. On sait que ${\displaystyle 41}$ est premier et congru à 1 modulo 4. D'après le critère d'Euler, ${\displaystyle 5^{\frac {41-1}{2}}=5^{20}=1}$ donc ${\displaystyle 5}$ est bien un résidu quadratique. (Comme avant, les opérations sont implicitement modulo ${\displaystyle 41}$).

1. On écrit ${\displaystyle p-1=40=5\cdot 2^{3}}$ d'où ${\displaystyle Q\leftarrow 5}$, ${\displaystyle S\leftarrow 3}$.
2. Recherche d'une valeur de ${\displaystyle z}$ :
   • ${\displaystyle 2^{\frac {41-1}{2}}=1}$ donc ${\displaystyle 2}$ est un résidu quadratique ;
   • ${\displaystyle 3^{\frac {41-1}{2}}=40=-1}$ donc 3 n'est pas un résidu quadratique : on pose ${\displaystyle z\leftarrow 3}$.
3. On pose :
   • ${\displaystyle M\leftarrow S=3}$ ;
   • ${\displaystyle c\leftarrow z^{Q}=3^{5}=38}$ ;
   • ${\displaystyle t\leftarrow n^{Q}=5^{5}=9}$ ;
   • ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2}$.
4. Boucle :
   • première itération :
     • ${\displaystyle t\neq 1}$ donc ce n'est pas fini ;
     • ${\displaystyle t^{2^{1}}=40}$, ${\displaystyle t^{2^{2}}=1}$ donc ${\displaystyle i\leftarrow 2}$ ;
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$ ;
     • ${\displaystyle M\leftarrow i=2}$ ;
     • ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$ ;
     • ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$ ;
     • ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$ ;
   • deuxième itération :
     • ${\displaystyle t\neq 1}$ donc ce n'est toujours pas fini ;
     • ${\displaystyle t^{2^{1}}=1}$ donc ${\displaystyle i\leftarrow 1}$ ;
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$ ;
     • ${\displaystyle M\leftarrow i=1}$ ;
     • ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$ ;
     • ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$ ;
     • ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$ ;
   • troisième itération :
     • ${\displaystyle t=1}$ donc c'est fini : renvoyer ${\displaystyle r=R=28}$.

En effet, on a bien ${\displaystyle 28^{2}=5{\bmod {4}}1}$. L'algorithme fournit donc les deux solutions de notre congruence, ${\displaystyle 28}$ et ${\displaystyle -28=13}$.

L'algorithme de Tonelli-Shanks peut naturellement être utilisé pour tout processus nécessitant le calcul de racine carrée modulo un nombre premier. Par exemple, il permet de déterminer des points sur des courbes elliptiques. Il est également utile pour les calculs de l'algorithme de signature de Rabin (en) et pour l'étape de criblage dans le crible quadratique.

De façon plus anecdotique, pour un nombre premier ${\displaystyle p\equiv 1{\bmod {4}}}$, il peut être utilisé pour déterminer ${\displaystyle a}$ et ${\displaystyle b}$ tels que ${\displaystyle p=a^{2}+b^{2}}$.

La méthode de Tonelli-Shanks peut être étendue à n'importe quel groupe cyclique (à la place de ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$) et à la recherche de racines ${\displaystyle k}$-ièmes pour tout entier ${\displaystyle k}$, en particulier pour le calcul d'une racine ${\displaystyle k}$-ième d'un élément d'un corps fini^[5].

S'il est nécessaire de calculer un grand nombre de racines carrées dans le même groupe cyclique et que S n'est pas trop grand, il est pertinent de préparer un tableau des racines carrées des éléments d'ordre 2 à l'avance, ce qui conduit à l'algorithme simplifié et accéléré suivant :

1. Diviser par 2 de façon répétée pour calculer ${\displaystyle Q}$ et ${\displaystyle S}$ tels que ${\displaystyle p-1=Q2^{S}}$ et ${\displaystyle Q}$ est impair.
2. Poser ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}}$ et ${\displaystyle t\leftarrow n^{Q}\equiv R^{2}/n}$.
3. Trouver ${\displaystyle b}$ dans la table tel que ${\displaystyle b^{2}=t}$ et poser ${\displaystyle R=R/b}$.
4. Renvoyer ${\displaystyle R}$.

Algorithme de Tonelli modulo ${\displaystyle p^{\lambda }}$

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

On lit dans le livre History of the theory of numbers de Leonard Eugene Dickson^[3] :

A. Tonelli^[6] a donné une formule explicite pour les racines de ${\displaystyle x^{2}\equiv c\!\!\!{\pmod {p^{\lambda }}}}$, lorsque ${\displaystyle p}$ est un nombre premier impair et qu'un non-résidu quadratique ${\displaystyle g}$ de ${\displaystyle p}$ est connu.

Dickson donne des indications mais elles sont désagréables à suivre. Cependant, la référence de Dickson^[3] montre clairement que l'algorithme de Tonelli fonctionne aussi bien modulo ${\displaystyle p^{\lambda }}$ que modulo ${\displaystyle p}$.