ECDLP / Generic prime-order groups · classical square-root storage

Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm

Steven D. Galbraith · Ping Wang · Fangguo Zhang

Advances in Mathematics of Communications 2017

PublishedSource checked

Time bound: O(sqrt(r)) group operations; improved average-case constants
Space bound: O(sqrt(r)) group elements

Source / version date: 28 Jun 2015
Comparison variant: Generic prime-order groups · classical square-root storage
Cost scale: r^c+o(1) group operations
coefficientExact: 1/2

Assumptions and source notes

Improved baby-step/giant-step methods for ECDLP with square-root storage. The exponent is still 1/2; the paper improves operation constants and analyses average-case performance, including heuristic components. No exponent improvement is claimed.

Source location

Introduction; Sections 2–5
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@misc{gwz15,
  author = {Steven D. Galbraith and Ping Wang and Fangguo Zhang},
  title = {{Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm}},
  journal = {Advances in Mathematics of Communications 11(3), 453–469},
  year = {2017},
  doi = {10.3934/amc.2017038},
  url = {https://eprint.iacr.org/2015/605},
  keywords = {elliptic curves, baby-step giant-step, negation map},
  cr_date = {2015-06-28},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Advances in Mathematics of Communications 11(3), 453–469},
  cr_author_ids = {steven-d-galbraith; ping-wang; fangguo-zhang}
}