On the discrete logarithm problem in finite fields of fixed characteristic

Granger, Robert, Kleinjung, Thorsten and Zumbrägel, Jens (2018) On the discrete logarithm problem in finite fields of fixed characteristic Transactions of the American Mathematical Society, 370 (5). pp. 3129-3145.

Preview

Text tran7027_AM.pdf - Accepted version Manuscript Download (316kB) | Preview

Abstract

For q a prime power, the discrete logarithm problem (DLP) in Fq consists in finding, for any g ∈ F × q and h ∈ hgi, 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 Fpn 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 Fpn in expected quasi-polynomial time.

Item Type:	Article
Divisions :	Faculty of Engineering and Physical Sciences > Computing Science
Authors :	Name Email ORCID Granger, Robert r.granger@surrey.ac.uk Kleinjung, Thorsten Zumbrägel, Jens
Date :	May 2018
DOI :	10.1090/tran/7027
Copyright Disclaimer :	© Copyright 2017 American Mathematical Society This is a preliminary PDF of the author-produced manuscript that has been peer-reviewed and accepted for publication. It has not been copyedited, proofread, or finalized by AMS Production staff. Once the accepted manuscript has been copyedited, proofread, and finalized by AMS Production staff, the article will be published in electronic form as a "Recently Published Article" before being placed in an issue. That electronically published article will become the Version of Record. This preliminary version is available to AMS members prior to publication of the Version of Record, and in limited cases it is also made accessible to everyone one year after the publication date of the Version of Record. The Version of Record is accessible to everyone five years after publication in an issue.
Depositing User :	Clive Harris
Date Deposited :	06 Feb 2019 15:07
Last Modified :	31 May 2019 02:08
URI:	http://epubs.surrey.ac.uk/id/eprint/850386

Actions (login required)

View Item

Downloads