Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the discrete logarithm problem in finite fields of fixed characteristic


Authors: Robert Granger, Thorsten Kleinjung and Jens Zumbrägel
Journal: Trans. Amer. Math. Soc. 370 (2018), 3129-3145
MSC (2010): Primary 11Y16, 11T71
DOI: https://doi.org/10.1090/tran/7027
Published electronically: October 24, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For $ q$ a prime power, the discrete logarithm problem (DLP) in  $ \mathbb{F}_{q}$ consists of finding, for any $ g \in \mathbb{F}_{q}^{\times }$ and $ h \in \langle g \rangle $, an integer $ x$ such that $ g^x = h$. We present an algorithm for computing discrete logarithms with which we prove that for each prime $ p$ there exist infinitely many explicit extension fields  $ \mathbb{F}_{p^n}$ in which the DLP can be solved in expected quasi-polynomial time. Furthermore, subject to a conjecture on the existence of irreducible polynomials of a certain form, the algorithm solves the DLP in all extensions  $ \mathbb{F}_{p^n}$ in expected quasi-polynomial time.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11Y16, 11T71

Retrieve articles in all journals with MSC (2010): 11Y16, 11T71


Additional Information

Robert Granger
Affiliation: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
Email: robert.granger@epfl.ch

Thorsten Kleinjung
Affiliation: Institute of Mathematics, Universität Leipzig, 04109 Leipzig, Germany
Address at time of publication: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
Email: thorsten.kleinjung@epfl.ch

Jens Zumbrägel
Affiliation: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
Address at time of publication: Faculty of Computer Science and Mathematics, Universitẗ Passau, 94032 Passau, Germany
Email: jens.zumbraegel@uni-passau.de

DOI: https://doi.org/10.1090/tran/7027
Received by editor(s): April 27, 2016
Received by editor(s) in revised form: July 20, 2016
Published electronically: October 24, 2017
Additional Notes: The first author was supported by the Swiss National Science Foundation via grant number 200021-156420. This work was mostly done while the second author was with the Laboratory for Cryptologic Algorithms, EPFL, Switzerland, supported by the Swiss National Science Foundation via grant number 200020-132160, and while the third author was with the Institute of Algebra, TU Dresden, Germany, supported by the Irish Research Council via grant number ELEVATEPD/2013/82.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society