Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

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)

Identifiers

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⟩

Share

Metrics

Record views

512

Files downloads

1253