Finite-field DLP / Small characteristic · heuristic expressions

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

Razvan Barbulescu · Pierrick Gaudry · Antoine Joux · Emmanuel Thomé

Eurocrypt 2014

PublishedSource checked

Time bound: n^{O(log n)}, n = log₂ Q
Space bound: Not extracted from the source

Source / version date: 18 Jun 2013
Comparison variant: Small characteristic · heuristic expressions
Cost scale: Expression only

Assumptions and source notes

Heuristic quasi-polynomial DLP in finite fields of small characteristic; the abstract explicitly defines n as the bit-size of the field cardinality. This is a different scale from L_Q[1/4,c].

Source location

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

Primary source ↗

BibTeXDownload .bib

@misc{bgjt13,
  author = {Razvan Barbulescu and Pierrick Gaudry and Antoine Joux and Emmanuel Thomé},
  title = {{A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic}},
  journal = {EUROCRYPT 2014 (published as A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic)},
  year = {2014},
  doi = {10.1007/978-3-642-55220-5_1},
  url = {https://arxiv.org/abs/1306.4244},
  keywords = {discrete logarithms, small characteristic, quasi-polynomial},
  cr_date = {2013-06-18},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {EUROCRYPT 2014 (published as A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic)},
  cr_author_ids = {razvan-barbulescu; pierrick-gaudry; antoine-joux; emmanuel-thome}
}