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 (\mod 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 $𝐅_{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 (\mod 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 𝐅_{p}$ , un carré modulo $p$ .

Sortie :

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

Déroulement :

Étape 1 : on trouve un élément $a \in 𝐅_{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

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

pour déterminer si

a

convient.

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

a

satisfasse à la condition est

(p - 1) / (2 p)

. 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} = {(a + \sqrt{a^{2} - n})}^{(p + 1) / 2}

dans l'extension de corps

𝐅_{p^{2}} = 𝐅_{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 $𝐅_{13}$ , ceux qui interviennent dans la deuxième étape sont des éléments de $𝐅_{1 3^{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 $𝐅_{13}$ , c'est-à-dire que le symbole de Legendre $(10 | 13)$ est égal à 1. Pour cela, on peut utiliser le critère d'Euler : $(10 | 13) \equiv 1 0^{6} \equiv 1 (\mod 13)$ (par exemple parce que $1 0^{6} - 1 = (1 0^{3} - 1) (1 0^{3} + 1)$ et que $1 0^{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 : $7^{6} = 34 3^{2} \equiv 5^{2} \equiv 25 \equiv - 1 (\mod 13) .$ Ainsi, le choix de $a = 2$ convient.
Étape 2 : Calculer $x = {(a + \sqrt{a^{2} - n})}^{(p + 1) / 2} = {(2 + \sqrt{- 6})}^{7}$ dans $𝐅_{13} (\sqrt{- 6})$ :

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

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

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

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

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

Démonstration

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

La première partie de la preuve consiste à définir un corps $𝐅_{p^{2}} = 𝐅_{p} (\sqrt{a^{2} - n}) = {x + y \sqrt{a^{2} - n} : x, y \in 𝐅_{p}}$ . Pour simplifier, on note $ω = \sqrt{a^{2} - n}$ . Comme $a^{2} - n$ n'est pas un résidu quadratique, il n'a pas de racine carrée dans $𝐅_{p}$ . L'élément $ω$ 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 𝐅_{p}$ , leur somme est définie comme

(x_{1} + y_{1} ω) + (x_{2} + y_{2} ω) = (x_{1} + x_{2}) + (y_{1} + y_{2}) ω

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

(x_{1} + y_{1} ω) (x_{2} + y_{2} ω) = x_{1} x_{2} + x_{1} y_{2} ω + y_{1} x_{2} ω + y_{1} y_{2} ω^{2} = (x_{1} x_{2} + y_{1} y_{2} (a^{2} - n)) + (x_{1} y_{2} + y_{1} x_{2}) ω

.

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 $𝐅_{p^{2}}$ comme un analogue fini du corps des nombres complexes ( $ω$ étant l'analogue de i).

Le neutre de la somme est $0$ , ou plus formellement $0 + 0 ω$ . Pour $α = x + y ω \in 𝐅_{p^{2}}$ ,

α + 0 = (x + y ω) + (0 + 0 ω) = (x + 0) + (y + 0) ω = x + y ω = α

.

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

α \cdot 1 = (x + y ω) (1 + 0 ω) = (x \cdot 1 + 0 \cdot y (a^{2} - n)) + (x \cdot 0 + 1 \cdot y) ω = x + y ω = α

.

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 ω$ est $- x - y ω$ . On cherche un inverse de $α = x_{1} + y_{1} ω$ sous la forme $α^{- 1} = x + y ω$ . La condition $α α^{- 1} = 1$ s'écrit

(x_{1} + y_{1} ω) (x + y ω) = (x_{1} x + y_{1} y (a^{2} - n)) + (x_{1} y + y_{1} x) ω = 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} (a^{2} - n)}

,

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

.

Préliminaires (suite) : une « conjugaison »

Maintenant que l'on dispose d'une extension $𝐅_{p^{2}}$ de degré deux de $𝐅_{p}$ , on introduit un analogue de la conjugaison complexe. Il est clair que l'application $F$ qui à $α \in 𝐅_{p}$ associe $α^{p}$ envoie $0$ sur $0$ , $1$ sur $1$ et le produit de deux éléments $α$ et $β$ sur le produit de leurs images : $(α β)^{p} = α^{p} β^{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 $(α + β)^{p} = α^{p} + β^{p}$ . Autrement dit, $F$ est un morphisme de corps. Il est automatiquement injectif et, comme $𝐅_{p^{2}}$ est fini, il est également surjectif.

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

(x + y ω)^{p} = x - y ω

.

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

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

Validité de l'algorithme de Cipolla

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

x_{0}^{2} = {(a + ω)}^{p + 1} = (a + ω) (a + ω)^{p} = (a + ω) (a - ω) = a^{2} - ω^{2} = a^{2} - (a^{2} - n) = n

.

A priori, on sait seulement que $x_{0} \in 𝐅_{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 $𝐅_{p}$ , ces racines sont toutes les racines dans $𝐅_{p^{2}}$ . Cela montre que $x_{0}$ et $- x_{0}$ sont les racines de $x^{2} - n$ dans $𝐅_{p^{2}}$ , donc que $x_{0}, - x_{0} \in 𝐅_{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 $4 m + 2 k - 4$ multiplications, $4 m - 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 $𝐅_{p^{2}}$ , on a les deux égalités suivantes :

(x + y ω)^{2} = (x^{2} + y^{2} ω^{2}) + ({(x + y)}^{2} - x^{2} - y^{2}) ω,

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

{(x + y ω)}^{2} (a + ω) = (a d^{2} - b (x + d)) + (d^{2} - b y) ω,

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

En supposant que $p \equiv 1 (\mod 4),$ (dans le cas $p \equiv 3 (\mod 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 $(a + ω)$ , 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) > 8 m + 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}) mod p^{λ}

où

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

et

s = p^{λ - 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 $1 3^{3}$ est :

\sqrt{10} mod 1 3^{3} \equiv 1046

.

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

2^{- 1} 1 0^{(1 3^{3} - 2 \cdot 1 3^{2} + 1) / 2} mod 1 3^{3} \equiv 1086

On calcule maintenant $(2 + \sqrt{2^{2} - 10})^{1 3^{2} \cdot 7} mod 1 3^{3}$ et $(2 - \sqrt{2^{2} - 10})^{1 3^{2} \cdot 7} mod 1 3^{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.)

On trouve alors :

(2 + \sqrt{2^{2} - 10})^{1 3^{2} \cdot 7} mod 1 3^{3} \equiv 1540

et

(2 - \sqrt{2^{2} - 10})^{1 3^{2} \cdot 7} mod 1 3^{3} \equiv 1540

et, finalement :

1086 (1540 + 1540) mod 1 3^{3} \equiv 1046

,

qui est la bonne réponse.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cipolla's_algorithm » (voir la liste des auteurs).

↑ Cipolla (1903).
↑ Cipolla (1907).
1 2 Dickson (1919), p. 218.
↑ Richard Crandall et Carl Pomerance, Prime numbers : A computational perspective, New York, Springer, 2005, 2^e éd. (1^re éd. 2001), xv + 597 p. (ISBN 978-0-387-25282-7, DOI 10.1007/0-387-28979-8), p. 157.
↑ Matt Baker, « Cipolla's Algorithm for finding square roots mod p », sur people.math.gatech.edu (version du 25 mars 2017 sur archive.org).
↑ Gonzalo Tornaría, LATIN 2002: Theoretical Informatics, Springer, coll. « Lecture Notes in Computer Science » (n^o 2286), 2002, xiii + 630 p. (ISBN 978-3-540-43400-9, DOI 10.1007/3-540-45995-2_38), p. 430-434.
↑ Michele Cipolla, « Applicatione della teoria delle funzioni numeriche del second'ordine alla risoluzione della congruenza di secondo grado », Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche, Napoli, 3^e série, vol. 10,‎ 1904, p. 144-150 (lire en ligne).

Bibliographie

(it) Michele Cipolla, « Un metodo per la risoluzione della congruenza di secondo grado », Rendiconto dell'Accademia delle Scienze Fisiche e Matematiche, 3^e série, vol. 9,‎ 1903, p. 153-163 (zbMATH 34.0219.02)
(it) Michele Cipolla, « Sulla risoluzione apiristica delle congruenze binomie secondo un modulo primo », Mathematische Annalen, vol. 63,‎ 1907, p. 54-61 (DOI 10.1007/BF01448423, zbMATH 37.0231.02, lire en ligne)
Leonard Eugene Dickson, History of the Theory of Numbers, vol. 1 : Divisibility and primality, Washington, Carnegie Institution of Washington, 1919, 486 p. (lire en ligne)
Eric Bach et Jeffrey O. Shallit, Algorithmic number theory, vol. 1 : Efficient algorithms, Cambridge, MIT Press, 1996, 528 p. (ISBN 9780262526296)

Articles connexes

Algorithme de Tonelli-Shanks

Portail de l’algèbre

[Cipolla1903-1] Cipolla (1903).

[Cipolla1907-2] Cipolla (1907).

[Dickson1919218-3] 1 2 Dickson (1919), p. 218.

[4] Richard Crandall et Carl Pomerance, Prime numbers : A computational perspective, New York, Springer, 2005, 2^e éd. (1^re éd. 2001), xv + 597 p. (ISBN 978-0-387-25282-7, DOI 10.1007/0-387-28979-8), p. 157.

[5] Matt Baker, « Cipolla's Algorithm for finding square roots mod p », sur people.math.gatech.edu (version du 25 mars 2017 sur archive.org).

[6] Gonzalo Tornaría, LATIN 2002: Theoretical Informatics, Springer, coll. « Lecture Notes in Computer Science » (n^o 2286), 2002, xiii + 630 p. (ISBN 978-3-540-43400-9, DOI 10.1007/3-540-45995-2_38), p. 430-434.

[7] Michele Cipolla, « Applicatione della teoria delle funzioni numeriche del second'ordine alla risoluzione della congruenza di secondo grado », Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche, Napoli, 3^e série, vol. 10,‎ 1904, p. 144-150 (lire en ligne).

[1]

[2]

[3]

[4]

[5]

[6]

[7]