Algorithme de Cornacchia

En mathématiques, l'algorithme de Cornacchia est une procédure pour résoudre certaines équations diophantiennes généralisant l'équation de Pell-Fermat. Cet algorithme est nommé d'après le mathématicien italien Giuseppe Cornacchia qui l'a introduit en 1908[1], et parfois également attribué au mathématicien irlandais Henry Smith, sous le nom d'algorithme de Cornacchia-Smith[2],[3]. Plus spécifiquement, l'algorithme fournit une solution entière ${\displaystyle (x,y)}$ de l'équation ${\displaystyle x^{2}+dy^{2}=m}$, où ${\displaystyle 1\leq d<m}$, et les entiers ${\displaystyle d}$ et ${\displaystyle m}$ sont premiers entre eux.

Cet algorithme est d'un intérêt pratique majeur, car il permet notamment de trouver une représentation d'un premier ${\displaystyle p}$ comme la norme d'un élément d'une extension quadratique, une étape essentielle par exemple dans la preuve de primalité par courbes elliptiques. Pour cette tâche, l'algorithme de Cornacchia est plus efficace que les méthodes génériques à base de formes quadratiques ou de réduction de réseaux euclidiens[4],[5]. Une autre utilisation importante de l'algorithme de Cornacchia est la génération de courbes elliptiques à multiplication complexe[6].

Description de l'algorithme

Soit donc l'équation ${\displaystyle x^{2}+dy^{2}=m}$, où ${\displaystyle 1\leq d<m}$, et les entiers ${\displaystyle d}$ et ${\displaystyle m}$ sont premiers entre eux. On suppose ${\displaystyle (x,y)}$ également premiers entre eux.

On obtient d'abord ${\displaystyle x_{0}}$ tel que ${\displaystyle x_{0}^{2}=-d{\bmod {m}}}$, en utilisant n'importe quelle méthode de calcul de racines carrées modulaires. Si ${\displaystyle -d}$ n'est pas un résidu quadratique modulo ${\displaystyle m}$, l'équation de départ n'a pas de solution. Puis on déploie l'algorithme d'Euclide étendu sur la paire ${\displaystyle (x_{0},m)}$, ce qui donne la séquence suivante :

$${\displaystyle {\begin{aligned}x_{0}&=a_{0}m+r_{0}\\m&=a_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{i}&=a_{i+2}r_{i+1}+r_{i+2}\end{aligned}}}$$

On arrête lorsque l'on atteint un rang ${\displaystyle k}$ tel que ${\displaystyle r_{k}^{2}<m<r_{k-1}^{2}}$. Si ${\displaystyle m-r_{k}^{2}\neq 0{\bmod {d}}}$, l'équation de départ n'a pas de solution. Dans le cas contraire, on vérifie que ${\displaystyle (m-r_{k}^{2})/d}$ est un carré. Si ce n'est pas le cas, l'équation de départ n'a pas de solution. Sinon, on conclut en exhibant une solution$${\displaystyle x=r_{k},y={\sqrt {\frac {m-u^{2}}{d}}}.}$$

Les solutions de ce type sont dites primitives. Si maintenant on ne suppose plus ${\displaystyle (x,y)}$ premiers entre eux, alors ${\displaystyle \gcd(x,y)^{2}|m}$ ! en particulier, si ${\displaystyle m}$ est sans carrés, toutes les solutions de l'équation sont primitives. Sinon, on note ${\displaystyle g}$ tel que ${\displaystyle g^{2}|m}$ et on résout l'équation ${\displaystyle x'^{2}+dy'^{2}=m'}$ avec ${\displaystyle m'=m/g^{2}}$. Une solution non-primitive est alors obtenue en prenant ${\displaystyle (x,y)=(gx',gy')}$.

La description de Cornacchia ne contenait pas de preuve que cet algorithme est correct. Il a fallu pour cela attendre la fin du 20^e siècle, et plusieurs preuves très différentes ont depuis été proposées[7],[8],[9], dont un argument élégant de François Morain par réduction au problème de Thue[10]. L'algorithme de Cornacchia s'étend aisément à des anneaux plus larges que ${\displaystyle \mathbb {Z} }$, notamment l'anneau ${\displaystyle \mathbb {Z} [i]}$ des entiers de Gauss[11].

Références

1. (it) Giuseppe Cornacchia, « Su di un metodo per la risoluzione in numeri interi dell' equazione ${\displaystyle \sum _{h=0}^{n}C_{h}x^{n-h}=P}$ », Giornale di Matematiche di Battaglini 46,‎ 1908, p. 33-90
2. (en) Richard Crandall et Carl Pomerance, Prime numbers : A computational perspective, New York, NY, Springer, 2005, 597 p. (ISBN 978-0-387-28979-3, OCLC 68656057, BNF 44641980, lire en ligne), p 106
3. (la) Henry J. S. Smith, « De compositione numerorum primorum formae ${\displaystyle 4\lambda +1}$ ex duobus quadratis », Journal für die reine und angewandte Mathematik 50,‎ 1855, p. 91
4. (en-US) François Morain, « Implementing the asymptotically fast version of the elliptic curve primality proving algorithm », Mathematics of Computation, vol. 76, n^o 257,‎ 2007, p. 493–505 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/s0025-5718-06-01890-4, lire en ligne, consulté le 1^er mars 2018)
5. (en) Henri Cohen, A Course in Computational Algebraic Number Theory, Springer Berlin Heidelberg, 1993, 536 p. (ISBN 978-3-662-02945-9, OCLC 851379925, lire en ligne)
6. (en) Richard E. Blahut, Cryptography and secure communication, Cambridge, Cambridge University Press, 2014, 602 p. (ISBN 978-1-107-01427-5, OCLC 880922078, BNF 43850719, lire en ligne), p. 357
7. (en) Kenneth Hardy, Joseph B. Muskat et Kenneth S. Williams, « A Deterministic Algorithm for Solving ${\displaystyle n=fu^{2}+gv^{2}}$ in Coprime Integers ${\displaystyle u}$ and ${\displaystyle v}$ », Mathematics of Computation, vol. 55, n^o 191,‎ 1990, p. 327–343 (DOI 10.2307/2008809, lire en ligne, consulté le 1^er mars 2018)
8. (en) Julius M. Basilla, « On the solution of ${\displaystyle x^{2}+dy^{2}=m}$ », Proceedings of the Japan Academy, Series A, Mathematical Sciences 80, no. 5,‎ 2004, p. 40-41
9. (en) Julius M. Basilla et Hideo Wada, « On the solution of ${\displaystyle x^{2}-dy^{2}=\pm m}$ », Proceedings of the Japan Academy, Series A, Mathematical Sciences, vol. 81, n^o 8,‎ octobre 2005, p. 137–140 (ISSN 0386-2194, DOI 10.3792/pjaa.81.137, lire en ligne, consulté le 1^er mars 2018)
10. François Morain (dir. Jean-Louis François), Courbes elliptiques et tests de primalité, Lyon, Université Claude Bernard (thèse de doctorat en sciences), 1990, 187 p, Chapitre 2.
11. (en) Patrick Longa et Francesco Sica, « Four-Dimensional Gallant–Lambert–Vanstone Scalar Multiplication », Journal of Cryptology, vol. 27, n^o 2,‎ 1^er avril 2014, p. 248–283 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-012-9144-3, lire en ligne, consulté le 1^er mars 2018)