Generic-group discrete logarithms
Recover an exponent in a cyclic group from group operations; generic algorithms do not exploit a field or curve representation.
Classical · randomized low storage
Group order r; expected generic group operations; no representation-specific index calculus
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Monte Carlo methods for index computation (mod p)Mathematics of Computation 1978SourceBibTeX / detailsrandom-walk heuristic | Jul 1978 | O(sqrt(r)) expected group operations | O(1) group elements | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Group order r; expected generic group operations; no representation-specific index calculus
- Computation
- Classical randomized
- Rigor
- Heuristic random-walk model
- Instances
- prime-order cyclic groups
- Cost scale
- r^{c+o(1)} group operations
- Parameter
- r
- Description
- Generic random-walk upper bounds. Random-function assumptions for rho are distinct from unconditional generic lower bounds.
- Comparison rules
- Generic random-walk upper bounds. Random-function assumptions for rho are distinct from unconditional generic lower bounds. 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
- generic groups, rho, low storage