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

Razvan Barbulescu; Cécile Pierrot

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 for the whole range of applicability of NFS and lowers the asymptotic complexity from to in the medium characteristic case, and from to in the high characteristic case. Version 2 contains an erratum.

Note: Erratum for version 1.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. http://dx.doi.org/10.1112/S1461157014000369
Keywords: discrete logarithm problem
Contact author(s): razvan barbulescu @ imj-prg fr
History: 2015-10-19: revised; 2014-02-27: received; See all versions
Short URL: https://ia.cr/2014/147
License: CC BY

BibTeX

@misc{cryptoeprint:2014/147,
      author = {Razvan Barbulescu and Cécile Pierrot},
      title = {The Multiple Number Field Sieve for Medium and High Characteristic > Finite Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/147},
      year = {2014},
      url = {https://eprint.iacr.org/2014/147}
}