You are looking at a specific version 20140227:204520 of this paper. See the latest version.

Paper 2014/147

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

Razvan Barbulescu and Cécile Pierrot

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problem
Contact author(s)
razvan barbulescu @ inria fr
History
2015-10-19: revised
2014-02-27: received
See all versions
Short URL
https://ia.cr/2014/147
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.