Skip to Main content Skip to Navigation
Theses

Algorithms for discrete logarithm in finite fields

Résumé : Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique
Document type :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01750438
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 12:46:15 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:09 PM

File

DDOC_T_2013_0183_BARBULESCU.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01750438, version 1

Collections

Citation

Razvan Barbulescu. Algorithms for discrete logarithm in finite fields. Other [cs.OH]. Université de Lorraine, 2013. English. ⟨NNT : 2013LORR0183⟩. ⟨tel-01750438⟩

Share

Metrics

Record views

93

Files downloads

151