Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Prime fields · classical heuristic
No deliberately supplied special-form modulus; includes full relation generation and logarithm computation
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | On the asymptotic complexity of computing discrete logarithms in the field GF(p)Diskretnaya Matematika 2003SourceBibTeX / detailsmultiple number fields theoretical asymptotics | 2003 | Lp[1/3, (92+26 sqrt(13))1/3/3] | Not extracted from the source | PublishedSource checked |
| 2 | Discrete Logarithms and Local UnitsPhilosophical Transactions of the Royal Society A 1993SourceBibTeX / details | 15 Nov 1993 | Lp[1/3, (64/9)1/3] | Not extracted from the source | PublishedSource checked |
| 3 | Discrete Logarithms in GF(P) Using the Number Field SieveSIAM Journal on Discrete Mathematics 1993SourceBibTeX / details | Feb 1993 | Lp[1/3, 32/3] | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- No deliberately supplied special-form modulus; includes full relation generation and logarithm computation
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- general prime fields F_p
- Cost scale
- L_p[1/3,c]
- Parameter
- p
- Description
- Prime-field NFS bounds. Precomputation cost and per-target logarithm cost should not be mixed. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Prime-field NFS bounds. Precomputation cost and per-target logarithm cost should not be mixed. 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
- prime fields, number field sieve, heuristic