Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Small characteristic · heuristic L(1/3)
p ≤ n^{o(√n)} in the cited function-field-sieve analysis
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | The Special Function Field SieveSIAM Journal on Discrete Mathematics 2002SourceBibTeX / details | 2002 | LQ[1/3, (32/9)1/3], Q=pn | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- p ≤ n^{o(√n)} in the cited function-field-sieve analysis
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- F_{p^n} with restricted characteristic
- Cost scale
- L_{p^n}[1/3,c]
- Parameter
- Q = p^n
- Description
- Fixed-alpha L(1/3) history only. Quasi-polynomial algorithms live in other categories. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Fixed-alpha L(1/3) history only. Quasi-polynomial algorithms live in other categories. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural. 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
- function field sieve, small characteristic, heuristic