ECDLP / Generic prime-order groups · classical low storage

Computing Elliptic Curve Discrete Logarithms with the Negation Map

Ping Wang · Fangguo Zhang

Information Sciences 2012

PublishedSource checked

Time bound: r^1/2+o(1) expected group operations
Space bound: Low-storage random walk; constant-size local state (plus distinguished-point storage for parallel variants)

Source / version date: 5 Jan 2011
Comparison variant: Generic prime-order groups · classical low storage
Cost scale: r^c+o(1) group operations
coefficientExact: 1/2

Assumptions and source notes

A rho/negation-map method for ordinary prime-order elliptic-curve subgroups. It addresses fruitless cycles and approaches a sqrt(2) speedup, which changes the multiplicative constant but leaves the leading exponent 1/2. The random-walk model remains heuristic.

Source location

Abstract; rho analysis
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@misc{wz11,
  author = {Ping Wang and Fangguo Zhang},
  title = {{Computing Elliptic Curve Discrete Logarithms with the Negation Map}},
  journal = {Information Sciences 195},
  year = {2012},
  url = {https://eprint.iacr.org/2011/008},
  keywords = {elliptic curves, rho, negation map, fruitless cycles},
  cr_date = {2011-01-05},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Information Sciences 195},
  cr_author_ids = {ping-wang; fangguo-zhang}
}