Faster individual discrete logarithms in non-prime finite fields with the NFS and FFS algorithms

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 in large and medium characteristic fields (e.g. GF$(p^2)$, GF$(p^{12})$); the Function Field Sieve and the Quasi Polynomial-time Algorithm in small characteristic finite fields (e.g. GF$(3^{6\cdot509})$). The last step of the NFS and FFS 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 of NFS and FFS, 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. The method we propose improves the initial splitting phase and applies to any finite field of composite extension degree. It exploits the available subfields with a cheap (polynomial-time) linear algebra step, resulting in a much more smooth decomposition of the target. This leads to a new trade-off in the asymptotic complexity of the initial splitting step: for instance it is improved by a factor 2 in the exponent for FFS and 2 1/3 in the exponent for NFS, for any finite field of even extension degree, and with a much smaller smoothness bound. In medium and large characteristic, it can be combined with Pomerance's Early Abort strategy. In small characteristic, it replaces the Waterloo algorithm of Blake, Fuji-Hara, Mullin and Vanstone. 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

Littérature citée [50 références]  Voir  Masquer  Télécharger
Contributeur : Aurore Guillevic <>
Soumis le : mardi 5 juillet 2016 - 05:21:06
Dernière modification le : lundi 7 août 2017 - 16:19:56
Document(s) archivé(s) le : jeudi 6 octobre 2016 - 10:10:19


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


  • HAL Id : hal-01341849, version 1


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


Aurore Guillevic. Faster individual discrete logarithms in non-prime finite fields with the NFS and FFS algorithms. 2016. 〈hal-01341849v1〉



Consultations de la notice


Téléchargements de fichiers