sparse strategies for composite elliptic-curve isogenies

[yyyyx4]

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

[sagetrac-git]

Changed commit from 09b8349 to 8dd58b7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8dd58b7

implement sparse strategy for prime-power isogenies

[sagetrac-git]

Changed commit from 8dd58b7 to 9012a31

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9012a31

implement sparse strategy for prime-power isogenies

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ac57648

Merge tag '9.8.beta2' into public/sparse_strategies_for_composite_elliptic_curve_isogenies

[sagetrac-git]

Changed commit from 9012a31 to ac57648

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f657363

Merge tag '9.8.beta3' into public/sparse_strategies_for_composite_elliptic_curve_isogenies

[sagetrac-git]

Changed commit from ac57648 to f657363

[mkoeppe]

Removed branch from the issue description because it has been replaced by PR #34965