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

Thorsten Kleinjung · Benjamin Wesolowski

Journal of the American Mathematical Society 2022

Time bound

(p n)^{2 log₂ n + O(1)} expected time, Q=pⁿ

Space bound

Not extracted from the source

Source / version date

25 Jun 2019

Comparison variant

Fixed characteristic · proven

Cost scale

Expression only

Assumptions and source notes

Proven expected-time bound for all finite fields of fixed characteristic. The factor 2 is retained in the expression; it is not converted into a generic 2^{cn} coefficient.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

@misc{kw19,
  author = {Thorsten Kleinjung and Benjamin Wesolowski},
  title = {{Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic}},
  journal = {Journal of the American Mathematical Society 35, 581–624},
  year = {2022},
  doi = {10.1090/jams/985},
  url = {https://arxiv.org/abs/1906.10668},
  keywords = {discrete logarithms, fixed characteristic, quasi-polynomial, unconditional},
  cr_date = {2019-06-25},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Journal of the American Mathematical Society 35, 581–624},
  cr_author_ids = {thorsten-kleinjung; benjamin-wesolowski}
}