Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Algorithmes de crible). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Université de Lorraine

1. Grémy, Laurent. 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.

Degree: Docteur es, Informatique, 2017, Université de Lorraine

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(pn). 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(p5) de taille 324 bits et l'autre dans un corps GF(p6) 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 finite fields GF(pn). In this thesis, we study the variants of the number field sieve (NFS) algorithm, which solve the most efficiently this problem, in the case where the characteristic of the field is medium. The NFS algorithm can be divided into four main steps: the polynomial selection, the relation collection, the linear algebra and the computation of an individual logarithm. We describe these steps and focus on the relation collection, one of the most costly steps. A way to perform it efficiently is to make use of sieve algorithms. Contrary to the classical case for which the relation collection takes place in a two-dimensional space, the finite fields we target require the enumeration of elements in a higher-dimensional space to reach the best theoretical complexity. There exist efficient sieve algorithms in two dimensions, but only a few in higher dimensions. We propose and study two new sieve algorithms allowing us to treat any dimensions, with an emphasis on the three-dimensional case. We have…

Advisors/Committee Members: Gaudry, Pierrick (thesis director), Videau, Marion (thesis director).

Subjects/Keywords: Cryptographie; Logarithme discret; Corps finis; Algorithmes de crible; Moyenne caractéristique; Implémentation; Calculs records; Réseaux euclidiens; Cryptography; Discrete logarithm; Finite fields; Sieve algorithm; Medium characteristic; Implementation; Record computations; Lattice; 005.8

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Grémy, L. (2017). 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. (Doctoral Dissertation). Université de Lorraine. Retrieved from http://www.theses.fr/2017LORR0141

Chicago Manual of Style (16th Edition):

Grémy, Laurent. “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.” 2017. Doctoral Dissertation, Université de Lorraine. Accessed June 20, 2019. http://www.theses.fr/2017LORR0141.

MLA Handbook (7th Edition):

Grémy, Laurent. “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.” 2017. Web. 20 Jun 2019.

Vancouver:

Grémy L. 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. [Internet] [Doctoral dissertation]. Université de Lorraine; 2017. [cited 2019 Jun 20]. Available from: http://www.theses.fr/2017LORR0141.

Council of Science Editors:

Grémy L. 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. [Doctoral Dissertation]. Université de Lorraine; 2017. Available from: http://www.theses.fr/2017LORR0141

.