Some cryptographic applications (most prominently, https://sike.org/) rely on computing isogenies of huge prime-power degrees quickly. The current algorithm used for this in Sage (since #32744) is quadratic in the number of prime-degree steps. It is known from the SIKE literature how to do better, replacing quadratic by quasilinear scaling.

This patch implements a simple version of the quasilinear algorithm. I haven't found any example where the change incurs a noticeable slowdown, while (as shown below) there can be quite significant speedups.

Example:

sage: F = GF((2^216*3^137-1, 2))
sage: E.<P,Q> = EllipticCurve(F, [1,0])
sage: %timeit E.isogeny(P, algorithm="factored")

Sage 9.7.beta6:

2.19 s ± 341 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

This branch:

1.04 s ± 13.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

CC: @defeo @JohnCremona @categorie

Component: elliptic curves

Author: Lorenz Panny

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