This patch introduces two important improvements for isogeny-minded users:

1. Implement EllipticCurveHom_composite, a type of elliptic-curve morphism that's fundamentally a formal composite map, but designed to behave almost exactly like EllipticCurveIsogeny. Leaving the isogeny decomposed can be exponentially more efficient in some scenarios (such as in cryptography).

2. Implement "factored" isogenies, that is, construction of an isogeny from a smooth-order kernel subgroup in time logarithmic in the degree (whereas EllipticCurveIsogeny is linear in the degree).

The new code is marked as experimental and not used anywhere by default, but adventurous users can opt-in by calling EllipticCurveHom_composite.make_default() or passing algorithm="factored" to E.isogeny(). Changes to the existing codebase are intentionally kept minimal.

Here's a diff without the dependency:

• sagemath/sagetrac-mirror@444330c...72ab0b8

Most of the algorithms are straightforward, except perhaps for equality testing: This relies on the fact that distinct isogenies cannot act the same on "too many" points (the bound is four times the degree). See also #31850.

Depends on #32502

CC: @defeo @JohnCremona @loefflerd

Component: elliptic curves

Keywords: elliptic curve isogenies

Author: Lorenz Panny, Lukas Zobernig

Branch: 72ab0b8

Reviewer: John Cremona

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