Finite-field DLP / Small characteristic · heuristic expressions

A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic

Antoine Joux

SAC 2013

PublishedSource checked

Time bound: L_Q(1/4+o(1))
Space bound: Not extracted from the source

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

Assumptions and source notes

Heuristic complexity under the source’s field-presentation and descent assumptions. Some input fields are embedded into an extension of degree at most 2 ceil(log_p n); do not assign a fake constant in a fixed L_Q[1/4,c] scale.

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{joux13,
  author = {Antoine Joux},
  title = {{A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic}},
  journal = {Selected Areas in Cryptography – SAC 2013},
  year = {2014},
  url = {https://eprint.iacr.org/2013/095},
  keywords = {discrete logarithms, small characteristic, index calculus},
  cr_date = {2013-02-21},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Selected Areas in Cryptography – SAC 2013},
  cr_author_ids = {antoine-joux}
}