Fast Algorithms for Towers of Finite Fields and Isogenies

Luca De Feo 1, 2
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Résumé : Dans cette thèse nous appliquons des techniques provenant du calcul formel et de la théorie des langages afin d'améliorer les opérations élémentaires dans certaines tours de corps finis. Nous appliquons notre construction au problème du calcul d'isogénies entre courbes elliptiques et obtenons une variante plus rapide (à la fois en théorie et en pratique) de l'algorithme de Couveignes. Le document est divisé en quatre parties. Dans la partie I nous faisons des rappels d'algèbre et de théorie de la complexité. La partie II traite du principe de transposition : nous généralisons des idées de Bostan, Schost et Lecerf et nous montrons qu'il est possible de transposer automatiquement des programmes sans pertes en complexité-temps et avec une petite perte en complexité-espace. La partie III combine les résultats sur le principe de transposition avec des techniques classiques en théorie de l'élimination ; nous appliquons ces idées pour obtenir des algorithmes asymptotiquement optimaux pour l'arithmétique des tours d'Artin-Schreier de corps finis. Nous décrivons aussi une implantation de ces algorithmes. Enfin, dans la partie IV nous utilisons les résultats précédents afin d'accélérer l'algorithme de Couveignes et de comparer le résultat avec les autres algorithmes pour le calcul d'isogénies qui font l'état de l'art. Nous présentons aussi une nouvelle généralisation de l'algorithme de Couveignes qui calcule des isogénies de degré inconnu.
Type de document :
Thèse
Mathematics [math]. Ecole Polytechnique X, 2010. English
Liste complète des métadonnées

https://tel.archives-ouvertes.fr/tel-00547034
Contributeur : Luca De Feo <>
Soumis le : mercredi 15 décembre 2010 - 14:15:15
Dernière modification le : vendredi 6 février 2015 - 13:13:51
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:51:09

Identifiants

  • HAL Id : tel-00547034, version 1

Citation

Luca De Feo. Fast Algorithms for Towers of Finite Fields and Isogenies. Mathematics [math]. Ecole Polytechnique X, 2010. English. <tel-00547034v1>

Partager

Métriques

Consultations de
la notice

42

Téléchargements du document

134