Applications cryptographiques des courbes modulaires

Abstract

Ce travail a pour but de chercher des familles infinies de courbes elliptiques rationnelles les mieux adaptées pour l'algorithme ECM de factorisation d'un nombre, en utilisant des courbes elliptiques. On établit un lien entre cette classification et le ``Programme B'' de Mazur, dont le but est de classifier toutes les courbes elliptiques ayant une image de Galois adélique contenu en $H$, un sous-groupe donné de $\mathrm{GL}_2(\hat{\mathbb{Z}})$.En se basant sur des travaux récents qui calculent des modèles explicites de courbes modulaires pour des sous-groupes de congruences de niveau une puissance d'un nombre premier, nous montrons qu'il existe exactement 1525 familles distinctes de courbes elliptiques rationnelles dont l'image de Galois adélique est un produit cartésien de sous-groupes de niveau une puissance d'un nombre premier. Ceci fournit une liste exhaustive de courbes elliptiques mieux adaptées pour l’algorithme ECM dont moins de 25 étaient connues dans la littérature. On quantifie l'adaptabilité de ces familles à l’algorithme ECM en améliorant une heuristique commune qui dit que $\#\mathrm{E}(\mathbb{F}_p)$ est autant friable qu'un entier quelconque de même taille.