Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Small characteristic · heuristic expressions
Characteristic growth and field presentations as specified in each source
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristicSAC 2013SourceBibTeX / detailsfield embeddings heuristic descent | 21 Feb 2013 | LQ(1/4+o(1)) | Not extracted from the source | PublishedSource checked |
| — | A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristicEurocrypt 2014SourceBibTeX / detailsheuristic descent quasi-polynomial | 18 Jun 2013 | nO(log n), n = log₂ Q | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Characteristic growth and field presentations as specified in each source
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- small-characteristic finite fields
- Cost scale
- Expression only
- Parameter
- n = log₂ Q
- Description
- A chronology of complexity classes, including L(1/4+o(1)) and quasi-polynomial bounds. No artificial scalar exponent is assigned across these scales.
- Comparison rules
- A chronology of complexity classes, including L(1/4+o(1)) and quasi-polynomial bounds. No artificial scalar exponent is assigned across these scales. 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
- small characteristic, quasi-polynomial, heuristic