Elliptic Curve Isogenies: Mathematical Foundation

An isogeny between two elliptic curves E and E' over a field k is a non-constant rational map phi: E -> E' that is also a group homomorphism — it maps the group law of E to the group law of E'. Every isogeny phi has a dual isogeny phi_hat: E' -> E such that phi_hat composed with phi equals multiplication-by-deg(phi) on E. The degree of an isogeny is the size of its kernel: a degree-l isogeny has a kernel of size l. Isogenies generalize scalar multiplication: multiplication by n is an isogeny from E to itself of degree n^2. Isogenies over finite fields are computed as rational functions (polynomials) that can be evaluated efficiently.

Velu's formulas (1971) provide explicit formulas for computing an isogeny phi: E -> E/G given a subgroup G of E. The image curve E/G = E' and the rational map phi are completely determined by G. Velu's formulas compute the image curve coefficients and the rational map as rational functions of degree equal to |G|. For a kernel subgroup G of prime order l, the isogeny has degree l and can be computed in O(l) operations. sqrt-Velu algorithms (Bernstein et al., 2019) reduce this to O(sqrt(l)) operations for large l, enabling CSIDH's efficient large-prime isogenies. Velu's formulas are the computational workhorse of all isogeny-based cryptography.