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

2 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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)}$.
Document type :
Journal articles
Domain :

https://hal.archives-ouvertes.fr/hal-03347994
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Friday, September 17, 2021 - 4:27:47 PM
Last modification on : Tuesday, October 19, 2021 - 11:06:00 PM

File

dlp.pdf
Files produced by the author(s)

Citation

Thorsten Kleinjung, Benjamin Wesolowski. Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic. Journal of the American Mathematical Society, American Mathematical Society, inPress, ⟨10.1090/jams/985⟩. ⟨hal-03347994⟩

Record views