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

Date: received 25 Jun 2019

Contact author: bj wesolowski at orange fr

Available format(s): PDF | BibTeX Citation

Version: 20190625:200911 (All versions of this report)

Short URL: ia.cr/2019/751


[ Cryptology ePrint archive ]