Generic-group discrete logarithms
Recover an exponent in a cyclic group from group operations; generic algorithms do not exploit a field or curve representation.
Quantum · abelian groups
Coherent efficient group operations and order information as required
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing 1997SourceBibTeX / details | 30 Aug 1995 | poly(log r) quantum work with efficient coherent group arithmetic | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Coherent efficient group operations and order information as required
- Computation
- Quantum
- Rigor
- Provable
- Instances
- efficiently represented cyclic groups
- Cost scale
- Expression only
- Parameter
- log₂ r
- Description
- Quantum polynomial-time discrete logarithms; generic classical lower bounds do not apply to this computation model.
- Comparison rules
- Quantum polynomial-time discrete logarithms; generic classical lower bounds do not apply to this computation model. 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
- quantum, abelian groups, polynomial time