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. 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}
}
