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

* 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
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Keywords :
Document type :
Preprints, Working Papers, ...
Domain :

https://hal.inria.fr/hal-01052449
Contributor : Aurore Guillevic Connect in order to contact the contributor
Submitted on : Friday, November 28, 2014 - 7:05:25 PM
Last modification on : Saturday, October 16, 2021 - 11:26:06 AM
Long-term archiving on: : Friday, April 14, 2017 - 11:23:52 PM

### Files

gfpndl.pdf
Files produced by the author(s)

### Identifiers

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

### Citation

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