Modèles rationnels pour ECM et EECM
Mots clés: courbes elliptiques, factorisation.
Le but de ce projet est d’analyser des variantes de l’algorithme de factorisation ECM.
Résumé
L’algorithme de factorisation ECM a été initialement proposé par H. Lenstra en 1985. Des nombreuses variantes et optimisations ont par la suite été proposées, notamment par Suyama (1985), Brent (1986) et Montgomery (1987, 1992).
Les ajouts les plus importants à l’algorithme original consistent en la “phase 2”, et en l’utilisation de courbes avec une grande torsion rationnelle, et en l’optimisation de l’arithmétique des courbes.
La “phase 2” permet d’agrandir la borne de friabilité utilisée par l’algorithme. La “phase 1” permet en effet de capturer toute courbe qui aurait un cardinal composé de premiers en dessous d’une borne , alors que la “phase 2” permet d’y ajouter toute courbe qui aurait en plus un facteur plus grand, en dessous d’une borne .
L’utilisation de courbes spéciales sur permet de forcer les courbes à avoir une certaine structure de torsion modulo le facteurs à trouver. Cette structure de torsion augmente à son tour la probabilité que le cardinal de la courbe soit friable.
Outre le choix de courbes spécifiques, le choix de leur modèle est aussi crucial. Traditionnellement, on utilise des courbes sous forme de Montgomery, mais le modèle d’Edwards, introduit récemment par Bernstein, Birkner, Lange et Peters, offre une alternative performante, surtout pour la “phase 2”.
Le but de ce projet est d’implanter quelques variantes de ECM, en comparant différents choix pour les courbes et en analysant leur efficacité et probabilité de succès.
Il est conseillé d’utiliser la bibliothèque Pari pour les sous-routines (par ex.: test de primalité) et pour tester le code (par ex.: vérifier les formules d’addition).
Prérequis
- Familiarité avec les courbes elliptiques.
Objectifs
-
Implanter une version complète de ECM, comprenant une “phase 1” et une “phase 2”.
-
Implanter le plus d’améliorations possibles pour chaque étape. Le choix est vaste, l’étudiant sélectionnera les optimisations qui lui conviennent mieux.
-
Utiliser plusieurs modèles de courbes : Montgomery, Suyama, Edwards. Comparer les statistiques de friabilité et l’efficacité globale du modèle.
Références
- P. Zimmerman. 20 years of ECM.
- D. Bernstein, P. Birkner, T. Lange, C. Peters. ECM using Edwards curves.
- P. Montgomery. Speeding the Pollard and elliptic curve methods of factorization.
- A. Kruppa. Speeding up Integer Multiplication and Factorization.
- R. Barbulescu, J. Bos, C. Bouvier, T. Kleinjung, P. Montgomery. Finding ECM-friendly curves through a study of Galois properties
- R. Barbulescu. Familles de courbes adaptées à la factorisation des entiers.