Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves

Steven Galbraith · Anton Stolbunov

Applicable Algebra in Engineering, Communication and Computing 2013

Time bound

O~(q^1/4)

Space bound

Not stated in the checked source

Source / version date

31 May 2011

Comparison variant

Classical · horizontal isogenies

Cost scale

q^c+o(1)

scale-evidence

CJS Section 1 describes Galbraith–Stolbunov as fourth-root q

primary-source

https://arxiv.org/abs/1105.6331

Assumptions and source notes

The ordinary horizontal-isogeny random-walk method has q^{1/4} scale; this work improves practical constants, not that exponent. The paper reports an approximately 14-fold speedup on a 160-bit prime field.

Source location

Abstract; asymptotic scale also stated in CJS Section 1
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{gs11-isogeny,
  author = {Steven Galbraith and Anton Stolbunov},
  title = {{Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves}},
  year = {2013},
  url = {https://arxiv.org/abs/1105.6331},
  keywords = {ordinary isogenies, random walks, horizontal isogenies},
  cr_date = {2011-05-31},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Applicable Algebra in Engineering, Communication and Computing 24(2):107–131},
  cr_author_ids = {steven-galbraith; anton-stolbunov}
}