Grémy, Laurent
[Author]
;
Université de Lorraine
[Contributor];
Gaudry, Pierrick
[Contributor];
Videau, Marion
[Contributor]
Algorithmes de crible pour le logarithme discret dans les corps finis de moyenne caractéristique ; Sieve algorithms for the discrete logarithm in medium characteristic finite fields
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Electronic Thesis;
E-Book;
Text
Title:
Algorithmes de crible pour le logarithme discret dans les corps finis de moyenne caractéristique ; Sieve algorithms for the discrete logarithm in medium characteristic finite fields
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
La sécurité des systèmes cryptographiques à clef publique repose sur la difficulté de résoudre certains problèmes mathématiques, parmi lesquels se trouve le problème du logarithme discret sur les corps finis GF(p^n). Dans cette thèse, nous étudions les variantes de l’algorithme de crible algébrique, number field sieve (NFS) en anglais, qui résolvent le plus rapidement ce problème, dans le cas où la caractéristique du corps est dite moyenne. NFS peut être divisé en quatre étapes principales : la sélection polynomiale, la recherche de relations, l’algèbre linéaire et le calcul d’un logarithme individuel. Nous décrivons ces étapes, en insistant sur la recherche de relations, une des étapes les plus coûteuses. Une des manières efficaces de réaliser cette étape est d’utiliser des algorithmes de crible. Contrairement au cas classique où la recherche de relations est réalisée dans un espace à deux dimensions, les corps finis que nous ciblons requièrent une énumération d’éléments dans un espace de plus grande dimension pour atteindre la meilleure complexité théorique. Il existe des algorithmes de crible efficaces en deux dimensions, mais peu pour de plus grandes dimensions. Nous proposons et analysons deux nouveaux algorithmes de crible permettant de traiter n’importe quelle dimension, en insistant particulièrement sur la dimension trois. Nous avons réalisé une implémentation complète de la recherche de relations pour plusieurs variantes de NFS en dimensions trois. Cette implémentation, qui s'appuie sur nos nouveaux algorithmes de crible, est diffusée au sein du logiciel CADO-NFS. Nous avons pu valider ses performances en nous comparant à des exemples de la littérature. Nous avons également été en mesure d’établir deux nouveaux records de calcul de logarithmes discrets, l'un dans un corps GF(p^5) de taille 324 bits et l'autre dans un corps GF(p^6) de taille 422 bits ; The security of public-key cryptography relies mainly on the difficulty to solve some mathematical problems, among which the discrete logarithm problem on ...