Sage currently computes an isogeny of prime degree ℓ using ϴ(ℓ) base-field operations. We can achieve the same task in Õ(√ℓ) operations using the √élu algorithm; see https://velusqrt.isogeny.org.

This patch adds a fairly reasonable implementation of the algorithm to Sage. It works for odd-degree isogenies over all finite fields and can outperform the current EllipticCurveIsogeny class starting from degrees around 100, depending on the concrete performance of the underlying base-field and polynomial arithmetic.

The new code is marked as experimental and isn't used anywhere by default. After some real-world testing and careful benchmarking, we can (and should) let Sage automatically decide which implementation to use for a given input.

CC: @defeo @JohnCremona @categorie @sagetrac-bensmith @sagetrac-tanja @tscrim @videlec @slel @kwankyu

Component: elliptic curves

Author: Lorenz Panny

Branch: a0f4c4a

Reviewer: John Cremona, Travis Scrimshaw, Kwankyu Lee

Issue created by migration from https://trac.sagemath.org/ticket/34303