Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Fixed extension degree · classical heuristic
Q=p^n with n fixed and p growing
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Using number fields to compute logarithms in finite fieldsMathematics of Computation 2000SourceBibTeX / details | 24 May 1999 | LQ[1/3, (64/9)1/3], Q=pn, n fixed | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Q=p^n with n fixed and p growing
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- finite fields of arbitrary fixed extension degree
- Cost scale
- L_Q[1/3,c]
- Parameter
- Q
- Description
- NFS over a fixed-degree extension field. Includes the complete general-input discrete logarithm computation. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- NFS over a fixed-degree extension field. Includes the complete general-input discrete logarithm computation. 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
- number field sieve, fixed extension degree, heuristic