ECPP

Un ordinateur peut trouver un entier de mille chiffres qui ressemble fortement à un nombre premier. Mais une forte présomption n'est pas encore une preuve. ECPP fabrique alors une suite de contrôles que l'on peut conserver et refaire.

La méthode choisit une courbe elliptique adaptée au nombre étudié et suit l'addition de certains de ses points. Si les relations obtenues satisfont un critère précis, la question est ramenée à la primalité d'un entier plus petit. En répétant cette descente, ECPP aboutit à un certificat court à vérifier.

ECPP, pour Elliptic Curve Primality Proving, est une méthode de preuve de primalité. Elle s'applique à un entier candidat n. Elle construit une courbe elliptique dont les coefficients sont calculés modulo n, un point P sur cette courbe et un entier m lié à l'ordre attendu de son groupe de points. Les additions de points sont elles aussi effectuées modulo n.

Le certificat justifie que la courbe est non singulière modulo n et contrôle le lien entre m et l'ordre du point P : cet ordre doit diviser m. Les opérations utilisées doivent aussi être bien définies modulo n. Il isole alors un grand facteur premier q de m et fournit des relations de la forme $mP=\mathcal{O}mP=\backslash mathcal\; O$ et $\frac{m}{q}P\mathrm{\ne }\mathcal{O}\backslash frac\{m\}\{q\}P\backslash ne\backslash mathcal\; O$, où le symbole $\mathcal{O}\backslash mathcal\; O$ désigne le point neutre. Ces deux relations imposent que q divise l'ordre de P, donc l'ordre du groupe de points. Sous ces hypothèses, lorsque q dépasse la borne requise, le critère exclut l'existence d'un diviseur premier suffisamment petit de n. La primalité de n est alors ramenée à celle de q, puis le procédé recommence avec des entiers décroissants.

La recherche des courbes et des ordres convenables peut comporter des choix aléatoires ; la vérification du certificat obtenu est, elle, déterministe. La preuve enregistre les courbes, les points, les facteurs et les relations nécessaires. Un vérificateur n'a donc pas à refaire la recherche qui a produit le certificat.

On veut certifier l'entier n = 101. Le certificat propose la courbe définie modulo 101 par $y^2=x^3+x+3y^2=x^3+x+3$, le point P de coordonnées (4, 24), l'entier m = 87 et son facteur premier q = 29.

1. La courbe est non singulière modulo 101, car le plus grand commun diviseur de 4 + 27 × 9 = 247 et 101 vaut 1. Le point appartient à la courbe : 24² et 4³ + 4 + 3 ont tous deux pour reste 71 modulo 101.

2. Un comptage des points donne 87 points sur cette courbe, avec 87 = 3 × 29. Les additions donnent 2P = (57, 25), 3P = (24, 69) et 28P = (4, 77) = −P ; ainsi 29P = $\mathcal{O}\backslash mathcal\; O$, donc 87P = $\mathcal{O}\backslash mathcal\; O$, tandis que (87/29)P = 3P n'est pas le point neutre. Ces coordonnées et ces relations se contrôlent avec la loi d'addition des points d'une courbe elliptique, dont le calcul n'est pas développé dans cette fiche.

3. La borne du critère vaut environ (101^1/4 + 1)² ≈ 17,39. Le facteur q = 29 la dépasse. Sa primalité se contrôle séparément : aucun des nombres premiers 2, 3 et 5, tous inférieurs ou égaux à √29, ne divise 29.

Le cardinal m = 87, les relations 87P = $\mathcal{O}\backslash mathcal\; O$ et 3P ≠ $\mathcal{O}\backslash mathcal\; O$, les conditions de non-singularité et la primalité de 29 permettent donc d'appliquer le critère et de conclure que 101 est premier. Les calculs explicitement refaisables ici sont la non-singularité, l'appartenance de P, la factorisation de 87, la primalité de 29 et l'inégalité 29 > 17,39 ; la vérification des multiples indiqués demande la loi d'addition des points, et le comptage complet des points de la courbe vérifie séparément le cardinal 87.

Lorsqu'une recherche produit un très grand candidat premier, un test probabiliste suffit souvent à écarter rapidement les composés. ECPP devient préférable lorsqu'il faut joindre une preuve vérifiable au résultat.

Pour archiver ou transmettre une certification, on conserve le certificat ECPP avec l'entier. Le destinataire vérifie les relations enregistrées au lieu de reproduire les choix de courbes effectués pendant la recherche.

Pour des nombres modestes, la division par les petits nombres premiers ou une autre preuve élémentaire demande moins de préparation. ECPP prend son intérêt lorsque la taille rend ces contrôles directs peu pratiques et que la certitude doit rester contrôlable.

ECPP et test de nombre probablement premier. Un test probabiliste fournit une confiance dont on peut borner le risque d'erreur. ECPP produit un certificat : si ce certificat est valide, le verdict « premier » ne dépend plus d'une probabilité.

Preuve de primalité et factorisation. ECPP cherche à prouver qu'un entier n'a pas de diviseur non trivial. Une méthode de factorisation cherche au contraire à exhiber les facteurs d'un entier composé ; le type de résultat attendu tranche entre les deux tâches.

Construction et vérification. La construction peut essayer plusieurs courbes avant de trouver les bonnes données. La vérification reprend seulement les données retenues ; elle ne mesure donc pas le coût de la recherche initiale.

Un échec intermédiaire n'est pas un verdict. Si une courbe ne fournit pas l'ordre ou le grand facteur requis, le symptôme est une branche qui ne descend pas. Il faut choisir une autre courbe, et non déclarer le nombre composé.

Le grand facteur doit franchir la borne. Dans l'exemple n = 101, un facteur q inférieur ou égal à environ 17,39 ne suffirait pas au critère utilisé. Il faudrait obtenir un facteur plus grand ou changer de certificat.

Une liste de données n'est pas automatiquement une preuve. Une courbe singulière, un point hors de la courbe ou une relation de multiples fausse invalide le certificat. Le vérificateur doit contrôler chaque condition avant d'accepter la conclusion.

Le temps de construction et celui de vérification diffèrent. La description quasi-polynomiale concerne les performances de l'algorithme sous le cadre d'analyse annoncé. Elle ne garantit pas que chaque choix aléatoire conduira immédiatement à une courbe utilisable.

Le glossaire test de primalité replace ECPP parmi les méthodes qui décident si un entier est premier et distingue leurs types de garanties.

La fiche courbe elliptique approfondit la structure algébrique dont ECPP exploite les points sur un corps fini.