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, et parfois également attribué au mathématicien irlandais Henry Smith, sous le nom d'algorithme de Cornacchia-Smith. Plus spécifiquement, l'algorithme fournit une solution entière $(x,y)$ de l'équation $x^{2}+dy^{2}=m$, où $1\leq d<m$, et les entiers $d$ et $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 $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. Une autre utilisation importante de l'algorithme de Cornacchia est la génération de courbes elliptiques à multiplication complexe.

Description de l'algorithme

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

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

$${\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 $k$ tel que $r_{k}^{2}<m<r_{k-1}^{2}$. Si $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 $(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$$x=r_{k},y={\sqrt {\frac {m-u^{2}}{d}}}.$$

Les solutions de ce type sont dites primitives. Si maintenant on ne suppose plus $(x,y)$ premiers entre eux, alors $\gcd(x,y)^{2}|m$ ! en particulier, si $m$ est sans carrés, toutes les solutions de l'équation sont primitives. Sinon, on note $g$ tel que $g^{2}|m$ et on résout l'équation $x'^{2}+dy'^{2}=m'$ avec $m'=m/g^{2}$. Une solution non-primitive est alors obtenue en prenant $(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, dont un argument élégant de François Morain par réduction au problème de Thue. L'algorithme de Cornacchia s'étend aisément à des anneaux plus larges que $\mathbb {Z}$, notamment l'anneau $\mathbb {Z} [i]$ des entiers de Gauss.