Finite-field DLP / Prime fields · classical heuristic

On the asymptotic complexity of computing discrete logarithms in the field GF(p)

D. V. Matyukhin

Diskretnaya Matematika 2003

PublishedSource checked

Time bound: L_p[1/3, (92+26 sqrt(13))^1/3/3]
Space bound: Not extracted from the source

Source / version date: 2003
Comparison variant: Prime fields · classical heuristic
Cost scale: L_p[1/3,c]
coefficientExact: (92+26 sqrt(13))^{1/3}/3

Assumptions and source notes

Modification of NFS DLP for prime fields with the same asymptotic heuristic constant as Coppersmith’s integer-factoring algorithm. Precomputation is included; no per-target/fixed-prime amortized cost is substituted.

Source location

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

Primary source ↗

BibTeXDownload .bib

@article{matyukhin03,
  author = {D. V. Matyukhin},
  title = {{On the asymptotic complexity of computing discrete logarithms in the field GF(p)}},
  journal = {Diskretnaya Matematika 15(1), 28–49; English translation Discrete Mathematics and Applications 13(1), 27–50},
  year = {2003},
  doi = {10.4213/dm184},
  url = {https://www.mathnet.ru/eng/dm184},
  keywords = {discrete logarithms, multiple number fields, prime fields},
  cr_date = {2003-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {Diskretnaya Matematika 15(1), 28–49; English translation Discrete Mathematics and Applications 13(1), 27–50},
  cr_author_ids = {d-v-matyukhin}
}