Composition of elliptic curve isogenies

[loefflerd]

Currently, composing two elliptic curve isogenies (with compatible domain and codomain) returns some sort of formal composite homomorphism, rather than an EllipticCurveIsogeny object:

sage: E = EllipticCurve(GF(3), [1, 0])                                          
sage: f = E.isogenies_prime_degree(7)[0]                                        
sage: E2 = f.codomain()                                                         
sage: g = E2.isogenies_prime_degree(7)[0]                                       
sage: g * f                                                                     
Composite map:
  From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 3
  To:   Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 3
  Defn:   Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3
        then
          Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 3
sage: type(g * f)                                                               
<class 'sage.categories.map.FormalCompositeMap'>

This is clearly suboptimal and can also return mathematically wrong answers with comparisons between isogenies (since it doesn't correctly detect when two compositions are equal). It would be nice if composing isogenies returned an EllipticCurveIsogeny object.

CC: @defeo @yyyyx4

Component: elliptic curves

Keywords: isogenies

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

[defeo]

comment:1

I'd love to see comparisions work, but you have to be careful how you rewrite the code.

Formal composition is the only way to keep isogeny chains from growing exponentially in size. There's tons of user code out there that constructs isogenies of degree, say, 2ⁿ by composing degree 2 isogenies, with an n that's way too big to actually compute and store the kernel polynomial. Blame isogeny based cryptography.

So the only way to make comparisons work would be to factor composite degree isogenies, rather than compose them.

I'm very much in favour of having Sage be smart about composite degree isogenies and systematically factor them, but that requires a serious overhaul of the isogeny code, that should be spread across many tickets.

[loefflerd]

comment:2

As a remark which applies equally to this ticket and my other isogenies ticket (#31851):

Something I've always liked about Sage is its openness to "toy implementations" -- code which solves a problem in a simple and direct way, even if it's far too slow for use in industrial-scale applications. You seem to be suggesting that there's no point in having the code in Sage at all, unless it's robust enough to work with examples that are so big that we might not be able to practically factorize the Frobenius discriminant. However, I'm not a cryptographer; I just want something that works in toy examples that I can play around with and show to my students -- for me q is more likely to be 3 or 17 than some 256-bit monster!

(I believe that the first time I heard the phrase "the perfect is the enemy of the good" was at a Sage Days workshop.)

Do you have evidence for the claim that there is lots of existing user code relying on the existing formal-composition approach to isogenies? If this is a genuine issue, then I guess we could compromise by having a separate method "composition_as_isogeny" or something, rather than overriding the default composition.

[defeo]

comment:5

Oh, I missed David's comment. I can only give anecdotal evidence for the existence of such code, but having been around summer research schools, I've seen lot of it.

Now, as I said I'm happy with any progress around isogenies, and am happy to review tickets that go in that direction (I'm even happy to write some code if I can spare some time, but I wouldn't count on that). My comment was just a warning about some obstacles that I think are better kept in mind when designing improvements. In particular, since the ticket mentioned equality, I maintain this is a tricky point, but it cannot be worse than the present situation, so on with the code!

Relatedly, I believe Hamish did a lot of thinking about how to represent (non-factored) isogenies in a canonical way in PARI/GP, so that equality tests are easy to perform. We may want to look at how it's done there, and reuse it or draw inspiration from it.

[yyyyx4]

comment:6

Replying to @loefflerd:

I guess we could compromise by having a separate method "composition_as_isogeny" or something, rather than overriding the default composition.

In my opinion, the best way to do this is to have the default composition be formal and implement all the usual methods such as .rational_maps() for the resulting factored isogenies. In fact, replacing the present generic formal composition morphisms by a smarter "composed isogeny" class is already work in progress.

Re: equality testing, I think the easiest way to do this is to check that the isogenies act identically on a few points that span a sufficiently large subgroup: Two isogenies of degree d must be equal if they agree on more than 4d points. (For finite base fields, acquiring a large enough subgroup may require field extensions, but the degree is polynomial.)

[yyyyx4]

comment:7

Replying to @yyyyx4:

In fact, replacing the present generic formal composition morphisms by a smarter "composed isogeny" class is already work in progress.

See #32744.

[yyyyx4]

comment:11

I think this should be resolved with #34410 (which, incidentally, needs a reviewer).