Elliptic-curve discrete logarithms
Compute discrete logarithms in elliptic-curve groups; distinguish ordinary cryptographic curves from anomalous or other exceptional families.
Prime fields · quantum resource bounds
Logical Toffoli count and logical qubits; no physical error-correction overhead
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Quantum Resource Estimates for Computing Elliptic Curve Discrete LogarithmsAsiacrypt 2017SourceBibTeX / detailslogical Toffoli gates logical qubits | 21 Jun 2017 | At most 448 n3 log₂(n) + 4090 n3 logical Toffoli gates | At most 9n + 2 ceil(log₂ n) + 10 logical qubits | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Logical Toffoli count and logical qubits; no physical error-correction overhead
- Computation
- Quantum
- Rigor
- Provable circuit analysis
- Instances
- elliptic curves over prime fields
- Cost scale
- Expression only
- Parameter
- n = ceil(log₂ p)
- Description
- Gate-level resource formulas for quantum ECDLP over prime fields.
- Comparison rules
- Gate-level resource formulas for quantum ECDLP over prime fields. 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, logical resources