Faster individual discrete logarithms in finite fields of composite extension degree

Aurore Guillevic 1, *
* Auteur correspondant
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms in large and medium characteristic fields (e.g., {GF}$(p^2)$, {GF}$(p^{12})$) are the Number Field Sieve and its variants (special, high-degree, tower). The best algorithms in small characteristic finite fields (e.g., {GF}$(3^{6 \cdot 509})$) are the Function Field Sieve, Joux's algorithm, and the quasipolynomial-time algorithm. The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains at the same level of difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any nonprime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step in small characteristic. Moreover it reduces the width and the height of the subsequent descent tree.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2018, pp.29. 〈http://www.ams.org/journals/mcom/〉. 〈10.1090/mcom/3376〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01341849
Contributeur : Aurore Guillevic <>
Soumis le : lundi 17 septembre 2018 - 11:08:52
Dernière modification le : lundi 22 octobre 2018 - 12:48:02

Fichiers

18_Guillevic_IndLog.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Relations

  • a comme partie hal-01157378 - This pre-print is a generalization of this previous work

Citation

Aurore Guillevic. Faster individual discrete logarithms in finite fields of composite extension degree. Mathematics of Computation, American Mathematical Society, 2018, pp.29. 〈http://www.ams.org/journals/mcom/〉. 〈10.1090/mcom/3376〉. 〈hal-01341849v3〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

25