Cryptology ePrint Archive: Report 2015/685

On the discrete logarithm problem in finite fields of fixed characteristic

Robert Granger and Thorsten Kleinjung and Jens Zumbrägel

Abstract: For $q$ a prime power, the discrete logarithm problem (DLP) in $\mathbb{F}_{q}^{\times}$ consists in finding, for any $g \in \mathbb{F}_{q}^{\times}$ and $h \in \langle g \rangle$, an integer $x$ such that $g^x = h$. For each prime $p$ we exhibit infinitely many extension fields $\mathbb{F}_{p^n}$ for which the DLP in $\mathbb{F}_{p^n}^{\times}$ can be solved in expected quasi-polynomial time.

Category / Keywords: public-key cryptography / discrete logarithm problem, finite fields, quasi-polynomial time algorithm

Date: received 7 Jul 2015

Contact author: thorsten kleinjung at epfl ch

Available format(s): PDF | BibTeX Citation

Note: In submission.

Version: 20150713:075227 (All versions of this report)

Short URL: ia.cr/2015/685

Discussion forum: Show discussion | Start new discussion