# The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields

* Corresponding author
Abstract : In this paper, we study the discrete logarithm problem in medium and high characteristic finite fields. We propose a variant of the Number Field Sieve~(NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3,(128/9)^{1/3})$ to $L_{p^n}(1/3,(2^{13}/3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n}(1/3,(64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26 \sqrt{13})/27))^{1/3})$ in the high characteristic case. Version 2 contains an erratum.
Keywords :
Document type :
Journal articles

Cited literature [21 references]

https://hal.inria.fr/hal-00952610
Contributor : Razvan Barbulescu <>
Submitted on : Thursday, October 15, 2015 - 3:29:12 PM
Last modification on : Thursday, December 10, 2020 - 10:45:50 AM
Long-term archiving on: : Thursday, April 27, 2017 - 4:49:55 AM

### File

MNFS_version2.pdf
Files produced by the author(s)

### Citation

Razvan Barbulescu, Cécile Pierrot. The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, 17, pp.230--246. ⟨10.1112/S1461157014000369⟩. ⟨hal-00952610v2⟩

Record views