The multiple number field sieve for medium- and high-characteristic finite fields

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 F-pn for the whole range of applicability of NFS and lowers the asymptotic complexity from L-pn(1/3,(128/9)(1/3)) to L-pn(1/3,(2(13)/3(6))(1/3)) in the medium characteristic case, and from L-pn(1/3,(64/9)(1/3)) to L-pn(1/3,((92+26 root 13)/27))(1/3)) in the high characteristic case.