Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Fixed characteristic · proven
F_{p^n}, with p fixed; randomized expected time
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristicJournal of the American Mathematical Society 2022SourceBibTeX / detailsunconditional quasi-polynomial | 25 Jun 2019 | (p n)2 log₂ n + O(1) expected time, Q=pn | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- F_{p^n}, with p fixed; randomized expected time
- Computation
- Classical randomized
- Rigor
- Provable
- Instances
- all extension fields of fixed prime characteristic
- Cost scale
- Expression only
- Parameter
- p,n
- Description
- Provable quasi-polynomial DLP in every extension field of fixed characteristic; infinite explicit subfamilies alone do not satisfy this category.
- Comparison rules
- Provable quasi-polynomial DLP in every extension field of fixed characteristic; infinite explicit subfamilies alone do not satisfy this category. Only compare entries with this cost scale, input domain and computational model. Polynomial and quasi-polynomial expressions without an extracted scalar are not ranked.
- Tags
- fixed characteristic, quasi-polynomial, unconditional