The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods

Cécile Pierrot 1
1 ALMASTY - ALgorithms for coMmunicAtion SecuriTY
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields. We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8(9 + 4√6)/15)^(1/3)), where F_Q is the target finite field and (8(9+4√6)/15)^(1/3)) ≈ 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q (1/3, 2.201). Similarly, combining MNFS with the Generalized Joux-Lercier method leads to an improvement on the asymptotic complexities in the boundary case between medium and high characteristic finite fields.
Type de document :
Communication dans un congrès
Eurocrypt, Apr 2015, Sofia, Bulgaria. Springer, 9056, pp.156-170, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-46800-5_7〉
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01056205
Contributeur : Cécile Pierrot <>
Soumis le : mercredi 20 août 2014 - 12:30:29
Dernière modification le : mercredi 21 mars 2018 - 18:58:20
Document(s) archivé(s) le : jeudi 27 novembre 2014 - 11:42:20

Fichier

Multiple_Number_Field_Sieve_wi...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas de modifications 4.0 International License

Identifiants

Collections

Citation

Cécile Pierrot. The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods. Eurocrypt, Apr 2015, Sofia, Bulgaria. Springer, 9056, pp.156-170, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-46800-5_7〉. 〈hal-01056205v2〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

79