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
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

https://hal.inria.fr/hal-01052449
Contributor : Aurore Guillevic <>
Submitted on : Friday, November 28, 2014 - 7:05:25 PM
Last modification on : Wednesday, April 3, 2019 - 1:22:58 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⟩

Share

Metrics

Record views

837

Files downloads

581