Computing isogenies between supersingular elliptic curves over F_p

Christina Delfs · Steven D. Galbraith

Designs, Codes and Cryptography 2016

Time bound

O~(p^1/4)

Space bound

Not stated in the checked source

Source / version date

29 Oct 2013

Comparison variant

F_p-rational curves · classical · heuristic

Cost scale

p^c+o(1)

input-restriction

Both supersingular curves defined over F_p

Assumptions and source notes

Both input curves are defined over F_p. Section 3 explicitly describes the runtime as heuristic; GRH supplies the class-group connectivity bound.

Source location

Section 3, Algorithm 1 and preceding complexity statement
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{dg13,
  author = {Christina Delfs and Steven D. Galbraith},
  title = {{Computing isogenies between supersingular elliptic curves over F_p}},
  year = {2016},
  url = {https://arxiv.org/abs/1310.7789},
  keywords = {supersingular isogenies, F_p, random walks},
  cr_date = {2013-10-29},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Designs, Codes and Cryptography 78(2):425–440},
  cr_author_ids = {christina-delfs; steven-d-galbraith}
}