Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the discrete logarithm problem in finite fields of fixed characteristic
HTML articles powered by AMS MathViewer

by Robert Granger, Thorsten Kleinjung and Jens Zumbrägel PDF
Trans. Amer. Math. Soc. 370 (2018), 3129-3145 Request permission

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
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
  • MR Author ID: 744248
  • 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
  • MR Author ID: 704259
  • 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
  • MR Author ID: 843678
  • Email: jens.zumbraegel@uni-passau.de
  • 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.
  • © Copyright 2017 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 370 (2018), 3129-3145
  • MSC (2010): Primary 11Y16, 11T71
  • DOI: https://doi.org/10.1090/tran/7027
  • MathSciNet review: 3766844