composite elliptic-curve isogenies

[yyyyx4]

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

[yyyyx4]

Dependencies: #32502

[yyyyx4]

Author: Lorenz Panny

[yyyyx4]

Branch: public/composite_elliptic_curve_isogenies

[yyyyx4]

Commit: e9ade97

[sagetrac-git]

Changed commit from e9ade97 to 7dd0390

[sagetrac-git]

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

7dd0390

fix typo

[sagetrac-git]

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

739312c

Merge tag '9.5.beta5' into public/composite_elliptic_curve_isogenies

[sagetrac-git]

Changed commit from 7dd0390 to 739312c

[sagetrac-git]

Changed commit from 739312c to 72ab0b8

[sagetrac-git]

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

753cd68	fix typo in docstring
72ab0b8	make linter happier

[yyyyx4]

comment:7

I've been using this code privately for a while now and it's very useful to me. I'm sure it would also be useful to others who work on similar things, so I think it would be really nice to get this into the 9.5 release. Can I convince anyone to review?

(To reemphasize, the code in this ticket is marked experimental and explicitly opt-in. The changes in the dependency #32502 should be strictly backwards compatible as well. Therefore, applying this shouldn't cause any real harm even if things are terribly broken.)

[JohnCremona]

comment:8

I am looking at it right now. If I do have suggestions, I'll try hard to make it so that they can be implemented in a later ticket. Thanks for doing this.

[JohnCremona]

comment:9

In the richcmp method, the code for curves over number fields does not do what the docstring says, and as written returns True/False if for just one point of infinite order (defined over the base field or a quadratic extension) the maps have the same image. I don't think this is what is intended.

How about: test a whole lot of random points, return False if they disagree on any, otherwise (if all the points pass this) do the harder work of comparing rational maps. I think the number of points to test should depend on the degree, 100 is rather overkill since over number fields it is very unlikely to see large degrees (the record in the LMFDB now is 147, see http://www.lmfdb.org/EllipticCurve/6.6.453789.1/1.1/a/). I should 10 would be plenty (before reverting to the exact test).

Task for the future: in computing the isogeny class C of an elliptic curve E over QQ, or over a number field, I only use prime degree isogenies, so while C.matrix() shows the full matrix of all pairwise degrees, C.isogenies() has a 0 (just a placeholder) in position (i,j) when the isogeny from the i'th to the j'th curve is not of prime degree. Using this new functionality we'll be able to fill those in too. But not on this ticket.

[yyyyx4]

comment:10

Thank you, John!

Replying to @JohnCremona:

In the richcmp method, the code for curves over number fields does not do what the docstring says, and as written returns True/False if for just one point of infinite order (defined over the base field or a quadratic extension) the maps have the same image. I don't think this is what is intended.

My reasoning was that the isogenies f,g to be compared are both group homomorphisms, hence if they agree on a single point P of infinite order, this extends to the entire subgroup generated by that point. Therefore, the difference f-g has infinite kernel (containing <P>), which implies f-g = 0 since (non-zero) isogenies have finite kernel by definition. Is this incorrect?

[JohnCremona]

comment:11

Your are certainly right, apologies for not seeing that. I had thought that you were avoiding points of finite order just to stay away from the kernel. It would have been nice to have had a comment to the effect that "if two isogenies agree on a point of infinite order then they must be equal", just as you explained, but never mind.

[JohnCremona]

Reviewer: John Cremona

[JohnCremona]

Changed keywords from none to elliptic curve isogenies

[yyyyx4]

comment:12

Thanks a lot for your time!

One question: Did you look at the entire diff including #32502, or just the changes made on top of #32502? In the first case, I think you can also set #32502 to "positive review".

[JohnCremona]

comment:13

I only looked at the diffs for this ticket. So I will go and look at the dependent ticket #32502 as well (probably not today though).

[vbraun]

Changed branch from public/composite_elliptic_curve_isogenies to 72ab0b8

[yyyyx4]

Changed commit from 72ab0b8 to none

[yyyyx4]

Changed author from Lorenz Panny to Lorenz Panny, Lukas Zobernig