Thèse de doctorat :
Algorithmes pour la factorisation d’entiers et le calcul de logarithme
discret
Délivré par l'Université de Lorraine.
Directeur de thèse : Paul Zimmermann.
Résumé :
Dans cette thèse, nous étudions les problèmes de la factorisation d'entier
et de calcul de logarithme discret dans les corps finis. Dans un premier
temps, nous nous intéressons à l'algorithme de factorisation d'entier ECM
et présentons une méthode pour analyser les courbes elliptiques utilisées
dans cet algorithme en étudiant les propriétés galoisiennes des polynômes
de division. Ensuite, nous présentons en détail l'algorithme de
factorisation d'entier NFS, et nous nous intéressons en particulier à
l'étape de sélection polynomiale pour laquelle des améliorations
d'algorithmes existants sont proposées. Puis, nous présentons les
algorithmes NFS-DL et FFS pour le calcul de logarithme discret dans les
corps finis. Nous donnons aussi des détails sur deux calculs de logarithme
discret effectués durant cette thèse, l'un avec NFS-DL et l'autre avec
FFS. Enfin, nous étudions une étape commune à l'algorithme NFS pour la
factorisation et aux algorithmes NFS-DL et FFS pour le calcul de
logarithme discret: l'étape de filtrage. Nous l'étudions en détail et nous
présentons une amélioration dont nous validons l'impact en utilisant des
données provenant de plusieurs calculs de factorisation et de logarithme
discret.
Manuscrit : [
Version adaptée à la lecture sur écran)
|
Version pour l'impression (couleur)
|
Version pour l'impression (noir et
blanc)
]
Soutenance :
[ pdf ]