Skip to Main content Skip to Navigation

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

Razvan Barbulescu 1 Pierrick Gaudry 1 Aurore Guillevic 2, 3 François Morain 3, *
* Corresponding author
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Aurore Guillevic <>
Submitted on : Friday, November 28, 2014 - 7:05:25 PM
Last modification on : Thursday, March 5, 2020 - 6:27:04 PM
Document(s) archivé(s) le : Friday, April 14, 2017 - 11:23:52 PM


Files produced by the author(s)


  • HAL Id : hal-01052449, version 4
  • ARXIV : 1408.0718



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



Record views


Files downloads