Cryptology ePrint Archive: Report 2019/751

Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic

Thorsten Kleinjung and Benjamin Wesolowski

Abstract: We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2\log_2(n) + O(1)}$.

Category / Keywords: public-key cryptography / discrete logarithm problem, finite field

Original Publication (with minor differences): Journal of the American Mathematical Society

Date: received 25 Jun 2019, last revised 10 Sep 2021

Contact author: bj wesolowski at orange fr

Available format(s): PDF | BibTeX Citation

Version: 20210910:115035 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]