Faster individual discrete logarithms in non-prime finite fields with the NFS and FFS algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2016

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

Résumé

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.
Fichier principal
Vignette du fichier
Guillevic16_indlog_HAL.pdf (627.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01341849 , version 1 (05-07-2016)
hal-01341849 , version 2 (06-08-2017)
hal-01341849 , version 3 (17-09-2018)

Identifiants

  • HAL Id : hal-01341849 , version 1

Citer

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

Relations

575 Consultations
529 Téléchargements

Partager

Gmail Facebook X LinkedIn More