Improvements to the number field sieve for non-prime finite fields - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Improvements to the number field sieve for non-prime finite fields

(1) , (1) , (2, 3) , (3)
1
2
3

Abstract

We propose various strategies for improving the computation of discrete logarithms in non-prime fields of medium to large characteristic using the Number Field Sieve. This includes new methods for selecting the polynomials; the use of explicit automorphisms; explicit computations in the number fields; and prediction that some units have a zero virtual logarithm. On the theoretical side, we obtain a new complexity bound of $L_{p^n}(1/3,\sqrt[3]{96/9})$ in the medium characteristic case. On the practical side, we computed discrete logarithms in $F_{p^2}$ for a prime number $p$ with $80$ decimal digits.
Nous décrivons plusieurs stratégies pour accélérer le calcul de logarithmes discrets dans un corps fini non premier de caractéristique moyenne ou grande à l'aide du crible algébrique. Parmi elles, de nouvelles méthodes de sélection polynomiale; l'utilisation explicite d'automorphismes; des calculs explicites dans les corps de nombres; et la prédiction de l'annulation des logarithmes virtuels d'unités bien choisies. D'un point de vue théorique, nous obtenons une complexité nouvelle en $L_{p^n}(1/3,\sqrt[3]{96/9})$ dans le cas de la caractéristique moyenne. Du côté pratique, nous avons mené à bien le calcul de logarithmes discrets dans $F_{p^2}$ avec $p$ premier de $80$ chiffres décimaux.
Fichier principal
Vignette du fichier
gfpndl.pdf (550.76 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01052449 , version 1 (26-07-2014)
hal-01052449 , version 2 (06-08-2014)
hal-01052449 , version 3 (26-08-2014)
hal-01052449 , version 4 (28-11-2014)
hal-01052449 , version 5 (24-08-2022)

Identifiers

Cite

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain. Improvements to the number field sieve for non-prime finite fields. 2014. ⟨hal-01052449v4⟩
893 View
671 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More