Computing isogenies between supersingular elliptic curves over F_p

Christina Delfs · Steven D. Galbraith

Designs, Codes and Cryptography 2016

Time bound

O~(p^1/2)

Space bound

Not stated in the checked source

Source / version date

29 Oct 2013

Comparison variant

General curves · classical · heuristic

Cost scale

p^c+o(1)

output

A composition of isogenies; not necessarily a fixed-degree short path

Assumptions and source notes

The F_p-subfield strategy gives a low-storage general isogeny-search method. The source uses random-walk heuristics; its F_p connectivity argument uses GRH. The p^{1/4} subroutine does not make the general algorithm p^{1/4}.

Source location

Section 4: The General Isogeny Problem
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}
}