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 low storage
Group order r; rho and negation-map variants; no anomalous-curve promise
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Computing Elliptic Curve Discrete Logarithms with the Negation MapInformation Sciences 2012SourceBibTeX / detailsnegation map random-walk heuristic | 5 Jan 2011 | r1/2+o(1) expected group operations | Low-storage random walk; constant-size local state (plus distinguished-point storage for parallel variants) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Group order r; rho and negation-map variants; no anomalous-curve promise
- Computation
- Classical randomized
- Rigor
- Heuristic random-walk model
- Instances
- prime-order elliptic-curve subgroups
- Cost scale
- r^{c+o(1)} group operations
- Parameter
- r
- Description
- Square-root ECDLP with low storage. Constant-factor improvements do not change the leading exponent 1/2.
- Comparison rules
- Square-root ECDLP with low storage. Constant-factor improvements do not change the leading exponent 1/2. 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, generic groups, rho, low storage