Cryptographic applications of modular curves
Institution:
Sorbonne universitéDisciplines:
Directors:
Abstract EN:
This work is aimed at finding and classifying all the families of ECM-friendly rational elliptic curves and quantifying their ECM-friendliness. We establish a link between the classification of ECM-friendly curves and Mazur's program B, which consists in classifying all the elliptic curves with the adelic Galois image contained in H, a subgroup of GL2(ˆZ). Building upon recent works which compute the models of modular curves associated to congruence subgroups of prime-power level, we prove that there are exactly 1525 distinct families of rational elliptic curves with distinct Galois images which are cartesian products of subgroups of prime-power level. This makes an exhaustive list of families of ECM-friendly rational elliptic curves, out of which less than 25 were previously known. Equipped with these families, we quantify their ECM-friendliness by improving a common heuristic which says that #E(Fp) is as smooth as a random integer of the same size.
Abstract FR:
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. et de quantifier cette adaptabilité. On établit un lien entre une 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 GL2(ˆ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 #E(Fp) est autant friable qu'un entier quelconque de même taille.