A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic

Guido Lido

Finite Fields and Their Applications 2026

Time bound

(log Q)^{O(log log Q)} expected time

Space bound

Not extracted from the source

Source / version date

22 Feb 2025

Comparison variant

Small characteristic · proven

Cost scale

Expression only

Assumptions and source notes

Theorem 1.1 covers all small-characteristic fields F_{p^n} with n > p, using elliptic presentations. Inspected theorem is in the revised 2025 version; record date therefore uses that version, not the 2022 first submission date.

Source location

Theorem 1.1; introduction definition of small characteristic
Version: arXiv:2206.10327v2, 2025-02-22

Primary source ↗

@misc{lido22,
  author = {Guido Lido},
  title = {{A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic}},
  journal = {Finite Fields and Their Applications 111, 102753},
  year = {2026},
  doi = {10.1016/j.ffa.2025.102753},
  url = {https://arxiv.org/abs/2206.10327},
  keywords = {discrete logarithms, small characteristic, quasi-polynomial, elliptic presentations},
  cr_date = {2022-06-13},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Finite Fields and Their Applications 111, 102753},
  cr_author_ids = {guido-lido}
}