Faster individual discrete logarithms with the QPA and NFS variants

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 known are the Number Field Sieve and its variants (special, high-degree, tower) in large and medium characteristic fields (e.g. $\mathrm{GF}(p^2)$, $\mathrm{GF}(p^{12})$); the Function Field Sieve and the Quasi Polynomial-time Algorithm in small characteristic finite fields (e.g. $\mathrm{GF}(3^{6 \cdot 509})$). 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 of same 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 non-prime 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 with QPA. Moreover it reduces the width and the height of the subsequent descent tree.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées
Contributeur : Aurore Guillevic <>
Soumis le : dimanche 6 août 2017 - 20:31:22
Dernière modification le : mardi 8 août 2017 - 01:09:00


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


  • HAL Id : hal-01341849, version 2



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


Aurore Guillevic. Faster individual discrete logarithms with the QPA and NFS variants. 2017. <hal-01341849v2>



Consultations de
la notice


Téléchargements du document