Finite-field discrete logarithms
Compute discrete logarithms in multiplicative groups of finite fields, separating prime fields, characteristic growth and extension structure.
Prime fields · quantum
Logical circuit and classical post-processing; assumptions stated per paper
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Extending Regev's factoring algorithm to compute discrete logarithmsPQCrypto 2024SourceBibTeX / detailsnumber-theoretic heuristic multiple quantum runs | 9 Nov 2023 | Regev-type polynomial-time quantum circuits and polynomial classical post-processing | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Logical circuit and classical post-processing; assumptions stated per paper
- Computation
- Quantum
- Rigor
- source dependent
- Instances
- prime fields
- Cost scale
- Expression only
- Parameter
- n = ceil(log₂ p)
- Description
- Quantum polynomial-time DLP for prime fields, with circuit size per run separate from total work and post-processing.
- Comparison rules
- Quantum polynomial-time DLP for prime fields, with circuit size per run separate from total work and post-processing. 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, quantum, polynomial time