Elliptic-curve discrete logarithms
Compute discrete logarithms in elliptic-curve groups; distinguish ordinary cryptographic curves from anomalous or other exceptional families.
Generic prime-order groups · classical square-root storage
Group order r; baby-step/giant-step variants; O(sqrt(r)) group-element storage
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step AlgorithmAdvances in Mathematics of Communications 2017SourceBibTeX / detailsbaby-step giant-step average-case constants | 28 Jun 2015 | O(sqrt(r)) group operations; improved average-case constants | O(sqrt(r)) group elements | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Group order r; baby-step/giant-step variants; O(sqrt(r)) group-element storage
- Computation
- Classical
- Rigor
- source-dependent average-case analysis
- Instances
- prime-order elliptic-curve subgroups
- Cost scale
- r^{c+o(1)} group operations
- Parameter
- r
- Description
- Baby-step/giant-step methods: square-root leading exponent and storage. The source distinguishes deterministic coverage from heuristic average-case constant analysis.
- Comparison rules
- Baby-step/giant-step methods: square-root leading exponent and storage. The source distinguishes deterministic coverage from heuristic average-case constant analysis. 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
- classical, baby-step giant-step, square-root storage