Algorithme de Cipolla

En théorie algorithmique des nombres, l'algorithme de Cipolla est une méthode pour résoudre une congruence de la forme

x^{2}\equiv n\!\!\!{\pmod {p}},

où $p$ est un nombre premier, $n$ est un entier donné et $x$ est un entier inconnu. Une fois fixé $p$ , il revient de résoudre l'équation $x^{2}=n$ dans le corps fini $\mathbf {F} _{p}$ à $p$ éléments, c'est-à-dire de trouver une racine carrée de $n$ dans ce corps. L'algorithme porte le nom de Michele Cipolla, le mathématicien italien qui l'a inventé en 1903^[1] avant de l'étendre aux équations de degré quelconque $x^{n}\equiv a\!\!\!{\pmod {p}}$ en 1907^[2].

Outre les modules premiers, l'algorithme de Cipolla permet également de calculer les racines carrées modulo les puissances d'un nombre premier^[3].

L'algorithme

Entrées :

$p$ , un nombre premier impair,
$n\in \mathbf {F} _{p}$ , un carré modulo $p$ .

Sortie :

$x\in \mathbf {F} _{p}$ tel que $x^{2}=n.$

Déroulement :

Étape 1 : on trouve un élément $a\in \mathbf {F} _{p}$ tel que $a^{2}-n$ n'est pas un carré.

On ne connaît pas d'algorithme déterministe pour trouver un tel élément

a

mais on peut utiliser la méthode essai-erreur suivante : on choisit un

a

au hasard et on calcule le symbole de Legendre

\left({\frac {a^{2}-n}{p}}\right)

pour déterminer si

a

convient.

La probabilité qu'un élément aléatoire

a

satisfasse à la condition est

(p-1)/(2p)

. Pour

p

suffisamment grand, elle est proche de

1/2

^[4]. On s'attend donc à faire environ deux essais avant de trouver une valeur convenable pour

a

.

Étape 2 : on calcule

x_{0}=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}

dans l'extension de corps

\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})

. Cet élément est solution de l'équation

x^{2}=n

.

NB : Si $x_{0}^{2}=n$ , alors $(-x_{0})^{2}=n$ également. Comme p est impair, $x_{0}\neq -x_{0}$ , si bien que dès que l'on a une solution $x_{0}$ , on en obtient une seconde, $-x_{0}$ .

Exemple

On fixe $p=13$ . Les éléments qui apparaissent dans la première étape sont des éléments de $\mathbf {F} _{13}$ , ceux qui interviennent dans la deuxième étape sont des éléments de $\mathbf {F} _{13^{2}}$ .

On chercher les $x$ tels que $x^{2}=10.$

Avant d'appliquer l'algorithme, il est préférable de vérifier que $10$ est bien un carré dans $\mathbf {F} _{13}$ , c'est-à-dire que le symbole de Legendre $(10|13)$ est égal à 1. Pour cela, on peut utiliser le critère d'Euler : ${\textstyle (10|13)\equiv 10^{6}\equiv 1{\pmod {13}}}$ (par exemple parce que $10^{6}-1=(10^{3}-1)(10^{3}+1)$ et que $10^{3}+1=1001=7\cdot 11\cdot 13$ ). Ainsi, 10 est un bien un carré modulo 13.

Étape 1 : Trouver un $a$ tel que $a^{2}-n$ n'est pas un carré. Comme indiqué, procède par tâtonnement. On part de $a=2$ , de sorte que $a^{2}-n=7$ . On calcule le symbole de Legendre $(7|13)$ à l'aide du critère d'Euler : ${\textstyle 7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\pmod {13}}.}$ Ainsi, le choix de $a=2$ convient.
Étape 2 : Calculer $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}$ dans $\mathbf {F} _{13}({\sqrt {-6}})$ :

\left(2+{\sqrt {-6}}\right)^{2}=4+4{\sqrt {-6}}-6=-2+4{\sqrt {-6}}

\left(2+{\sqrt {-6}}\right)^{4}=\left(-2+4{\sqrt {-6}}\right)^{2}=-1-3{\sqrt {-6}}

\left(2+{\sqrt {-6}}\right)^{6}=\left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)=9+2{\sqrt {-6}}

\left(2+{\sqrt {-6}}\right)^{7}=\left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)=6.

Ainsi, $x=6$ est une solution, de même que $-x=-6$ . De fait, on a bien ${\textstyle 6^{2}\equiv 10{\pmod {13}}.}$

Démonstration

Préliminaires : un corps de cardinal $p^{2}$

La première partie de la preuve consiste à définir un corps $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}$ . Pour simplifier, on note $\omega ={\sqrt {a^{2}-n}}$ . Comme $a^{2}-n$ n'est pas un résidu quadratique, il n'a pas de racine carrée dans $\mathbf {F} _{p}$ . L'élément $\omega$ peut donc être considéré comme un analogue du nombre complexe i. Les opérations sont faciles à définir. Pour $x_{1},x_{2},y_{1},y_{2}\in \mathbf {F} _{p}$ , leur somme est définie comme

\left(x_{1}+y_{1}\omega \right)+\left(x_{2}+y_{2}\omega \right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\omega

et leur produit se détermine en se rappelant que $\omega ^{2}=a^{2}-n$ , ce qui donne :

\left(x_{1}+y_{1}\omega \right)\left(x_{2}+y_{2}\omega \right)=x_{1}x_{2}+x_{1}y_{2}\omega +y_{1}x_{2}\omega +y_{1}y_{2}\omega ^{2}=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega

.

Il faut maintenant vérifier les propriétés du corps. L'addition et la multiplication étant bien définies, on vérifie qu'elles sont associatives, commutatives et que le produit est distributif sur la somme. C'est d'autant plus facile si l'on voit le corps $\mathbf {F} _{p^{2}}$ comme un analogue fini du corps des nombres complexes ( $\omega$ étant l'analogue de i).

Le neutre de la somme est $0$ , ou plus formellement $0+0\omega$ . Pour $\alpha =x+y\omega \in \mathbf {F} _{p^{2}}$ ,

\alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha

.

Le neutre du produit est $1$ , ou plus formellement $1+0\omega$ :

\alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot y\left(a^{2}-n\right)\right)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha

.

Il n'y a plus qu'à trouver des opposés et des inverses pour les éléments non nuls. On vérifie sans peine que l'opposé de $x+y\omega$ est $-x-y\omega$ . On cherche un inverse de $\alpha =x_{1}+y_{1}\omega$ sous la forme $\alpha ^{-1}=x+y\omega$ . La condition $\alpha \alpha ^{-1}=1$ s'écrit

(x_{1}+y_{1}\omega )(x+y\omega )=\left(x_{1}x+y_{1}y\left(a^{2}-n\right)\right)+\left(x_{1}y+y_{1}x\right)\omega =1

,

ce qui équivaut un système de deux équations : $x_{1}x+y_{1}(a^{2}-n)y=1$ et $y_{1}x+x_{1}y=0$ . Le déterminant de ce système est $x_{1}^{2}-y_{1}^{2}(a^{2}-n)$ . Supposons qu'il s'annule : si $y_{1}\neq 0$ , alors $a^{2}-n=(x_{1}/y_{1})^{2}$ , ce qui est absurde ; ainsi, $y_{1}=0$ , puis $x_{1}=0$ , ce qui est contraire aux hypothèses. Cela entraîne que le système a une unique solution, et donc qu'il y a un inverse unique, déterminé par

x={\frac {x_{1}}{x_{1}^{2}-y_{1}^{2}\left(a^{2}-n\right)}}

,

y=-{\frac {y_{1}}{x_{1}^{2}-y_{1}^{2}\left(a^{2}-n\right)}}

.

Préliminaires (suite) : une « conjugaison »

Maintenant que l'on dispose d'une extension $\mathbf {F} _{p^{2}}$ de degré deux de $\mathbf {F} _{p}$ , on introduit un analogue de la conjugaison complexe. Il est clair que l'application $F$ qui à $\alpha \in \mathbf {F} _{p}$ associe $\alpha ^{p}$ envoie $0$ sur $0$ , $1$ sur $1$ et le produit de deux éléments $\alpha$ et $\beta$ sur le produit de leurs images : $(\alpha \beta )^{p}=\alpha ^{p}\beta ^{p}$ . De plus, on sait que pour $p$ premier et $k$ compris entre $1$ et $p-1$ , le coefficient binomial ${\binom {p}{k}}$ est un multiple de $p$ : cela entraîne que $(\alpha +\beta )^{p}=\alpha ^{p}+\beta ^{p}$ . Autrement dit, $F$ est un morphisme de corps. Il est automatiquement injectif et, comme $\mathbf {F} _{p^{2}}$ est fini, il est également surjectif.

De plus, pour tout élément $x+y\omega \in \mathbf {F} _{p^{2}}$ , on a

(x+y\omega )^{p}=x-y\omega

.

En effet, comme $\omega ^{2}=a^{2}-n$ n'est pas un carré dans $\mathbf {F} _{p}$ , on a par le critère d'Euler $\omega ^{p-1}=\left(\omega ^{2}\right)^{(p-1)/2}=-1$ . Ainsi $\omega ^{p}=-\omega$ , ce qui avec le petit théorème de Fermat (qui stipule que $x^{p}=x$ pour tout $x\in \mathbf {F} _{p}$ ) donne la relation voulue : $(x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=x-y\omega$ .

Le morphisme $F$ est appelé automorphisme de Frobenius de $\mathbf {F} _{p^{2}}$ .

Validité de l'algorithme de Cipolla

Enfin, on montre que si $x_{0}=\left(a+\omega \right)^{(p+1)/2}\in \mathbf {F} _{p^{2}}$ , alors $x_{0}^{2}=n\in \mathbf {F} _{p}$ . On calcule, à l'aide de ce qui précède :

x_{0}^{2}=\left(a+\omega \right)^{p+1}=(a+\omega )(a+\omega )^{p}=(a+\omega )(a-\omega )=a^{2}-\omega ^{2}=a^{2}-\left(a^{2}-n\right)=n

.

A priori, on sait seulement que $x_{0}\in \mathbf {F} _{p^{2}}$ . Cependant, puisque sur un corps, un polynôme non nul de degré n possède au plus n racines dans tout corps K, et puisque $x^{2}-n$ a deux racines dans $\mathbf {F} _{p}$ , ces racines sont toutes les racines dans $\mathbf {F} _{p^{2}}$ . Cela montre que $x_{0}$ et $-x_{0}$ sont les racines de $x^{2}-n$ dans $\mathbf {F} _{p^{2}}$ , donc que $x_{0},-x_{0}\in \mathbf {F} _{p}$ ^[5].

Nombre d'opérations

Une fois trouvés une valeur convenable pour $a$ , le nombre d'opérations requises pour l'algorithme est $4m+2k-4$ multiplications, $4m-2$ sommes, où m est le nombre de chiffres dans l'écriture binaire de p et k le nombre de 1 dans cette représentation. Pour trouver $a$ par essai-erreur, le nombre moyen de calculs du symbole de Legendre est 2. Cela dit, on peut avoir de la chance dès le premier essai et il peut en falloir plus de deux. Dans le corps $\mathbf {F} _{p^{2}}$ , on a les deux égalités suivantes :

(x+y\omega )^{2}=\left(x^{2}+y^{2}\omega ^{2}\right)+\left(\left(x+y\right)^{2}-x^{2}-y^{2}\right)\omega ,

où $\omega ^{2}=a^{2}-n$ est déjà connu. Ce calcul nécessite 4 multiplications et 4 additions ;

\left(x+y\omega \right)^{2}\left(a+\omega \right)=\left(ad^{2}-b\left(x+d\right)\right)+\left(d^{2}-by\right)\omega ,

où $d=(x+ya)$ et $b=ny$ . Cette opération nécessite 6 multiplications et 4 sommes.

En supposant que $p\equiv 1{\pmod {4}},$ (dans le cas $p\equiv 3{\pmod {4}}$ , le calcul de $x\equiv \pm n^{\frac {p+1}{4}}$ est plus rapide), l'expression binaire de $(p+1)/2$ a $m-1$ chiffres, dont $k$ valent $1$ . Ainsi, pour calculer la puissance $(p+1)/2$ -ième de $\left(a+\omega \right)$ , la première formule doit être utilisée $n-k-1$ fois et la seconde $k-1$ fois.

Au bilan, l'algorithme de Cipolla est plus rapide que l'algorithme de Tonelli-Shanks si et seulement si $S(S-1)>8m+20$ , où $2^{S}$ est la plus grande puissance de 2 qui divise $p-1$ ^[6].

Équation modulo une puissance d'un nombre premier

D'après Dickson dans son History of numbers, la formule suivante due à Cipolla permet de trouver les racines carrées modulo les puissances des nombres premiers^[3]^,^[7] :

2^{-1}q^{t}((k+{\sqrt {k^{2}-q}})^{s}+(k-{\sqrt {k^{2}-q}})^{s}){\bmod {p^{\lambda }}}

où

t=(p^{\lambda }-2p^{\lambda -1}+1)/2

et

s=p^{\lambda -1}(p+1)/2

,

avec

q=10

,

k=2

dans l'exemple précédent

En reprenant l'exemple ci-dessus, on peut vérifier que cette formule calcule bien des racines carrées modulo les puissances d'un nombre premier.

On va vérifier qu'une racine de $10$ modulo $13^{3}$ est :

{\sqrt {10}}{\bmod {13^{3}}}\equiv 1046

.

On calcule d'abord $2^{-1}q^{t}$ :

2^{-1}10^{(13^{3}-2\cdot 13^{2}+1)/2}{\bmod {13^{3}}}\equiv 1086

On calcule maintenant $(2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}$ et $(2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}$ (on trouve ici (en) un code Mathematica qui effectue ce calcul, que l'on peut comprendre par analogie avec un calcul sur les nombres complexes avec des coefficients modulo 13 au lieu d'être réels.)