Skip to Main content Skip to Navigation
Journal articles

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

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
Complete list of metadata

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)

Identifiers

Collections

CNRS | IMB | INRIA

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⟩

Share

Metrics

Record views

43

Files downloads

47