scalar-multiplication endomorphisms of elliptic curves

[yyyyx4]

This ticket adds EllipticCurveHom_scalar, a new class encapsulating scalar multiplications on elliptic curves. This serves two main purposes:

1. It solves one of the motivations behind Make EllipticCurveIsogeny objects faster to create via lazy evaluation #8014 (faster multiplication_by_m_isogeny).
2. Wrapping scalar multiplications as an EllipticCurveHom is an important step towards implementing endomorphism rings (see Meta-ticket: Further work on isogenies and endomorphisms of elliptic curves #7368).

We also deprecate .multiplication_by_m_isogeny(): It should be replaceable by .scalar_multiplication() in all cases.

Depends on #32502
Depends on #32744
Depends on #33865

CC: @defeo @JohnCremona @tscrim @videlec @fchapoton @kwankyu

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: 884263e

Reviewer: John Cremona

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

[yyyyx4]

Dependencies: #32502, #32744

[yyyyx4]

Commit: 64865d2

[yyyyx4]

Last 10 new commits:

80b0bb1	reflect this change in the documentation
894b145	Merge tag '9.5.beta3' into public/make_WeierstrassIsomorphism_behave_like_EllipticCurveIsogeny
47db3b1	Merge branch 'public/make_WeierstrassIsomorphism_behave_like_EllipticCurveIsogeny' into composite_elliptic_curve_isogenies
bdce391	introduce EllipticCurveHom_composite
e9ade97	make EllipticCurveHom_composite available from EllipticCurve_field.isogeny
7dd0390	fix typo
739312c	Merge tag '9.5.beta5' into public/composite_elliptic_curve_isogenies
753cd68	fix typo in docstring
72ab0b8	make linter happier
64865d2	scalar-multiplication endomorphisms

[yyyyx4]

Branch: public/scalar_elliptic_curve_endomorphisms

[yyyyx4]

Author: Lorenz Panny

[JohnCremona]

comment:2

This is a great idea. Why not just call these endomorphisms, i.e. call the class something like EllipticCurveEndomorphism instead of EllipticCurveHom_scalar? I don' know if there is a plan to late include more general endomorphisms (CM in char. 0, and both the ordinary and supersingular possibilities in char.p), but even if we are not going to implement those now, we could set it up to that the class EllipticCurveEndomorphism exists and (say) EllipticCurveScalarEndomorphism is a subclass doing what this class EllipticCurveHom_scalar does.

[yyyyx4]

comment:3

Thank you, that's a very good remark! I can see that there are several ways to "slice up" the space of objects we're trying to model here. My reasoning was the following (very much up for discussion):

• There's no real reason to separate isogenies and endomorphisms at this level — they can all be child classes of EllipticCurveHom with a common interface. Some EllipticCurveHoms are of course endomorphisms, but we don't have to treat them specially. (Note: .is_endomorphism() already works.)
• On the level of those maps, we can easily implement formal compositions (composite elliptic-curve isogenies #32744) and sums (to be done). Multiplication in the endomorphism ring "just works", as does composing endomorphisms with isogenies (thus, we prevent incompatibilities like we've been having with isomorphisms; cf. elliptic-curve isogenies probably shouldn't be mutable #32388, make WeierstrassIsomorphism behave (more) like EllipticCurveIsogeny #32502).
• The parent object of any EllipticCurveHom should be a hom-module that knows about the domain and codomain curve, regardless of what kind of EllipticCurveHom implementation it is. Of course, some of those hom-modules will be closed under composition, but again we don't have to do anything special here. (Side effect: Composing isogenies E -> E' -> E won't require any special treatment either.)
• Now, none of these objects knows a lot about its own structure. This mandates the last ingredient: An EndomorphismRing object that encapsulates both the algebraic view of an endomorphism ring (i.e., a quadratic order or a quaternion order) and a mapping of the generators of that abstract ring to explicit EllipticCurveHoms. With that, we can first use all the tools available for quadratic fields and quaternion algebras in the abstract world, then "project down" the situation to the corresponding maps on curves. (At least in principle, it should be possible to handle these translations almost seamlessly by overloading some methods.)
• Note that such a ring of endomorphisms need not be the (full) ring of endomorphisms: Subrings that could prove useful (especially for big instances where we cannot always compute the full endomorphism ring) include the Frobenius order, or some rank-2 subring of a quaternionic endomorphism ring.

I imagine that this design will make it relatively straightforward to implement things like computing endomorphism rings (#31851), or embedding a bunch of explicitly given EllipticCurveHoms into an abstract quadratic or quaternionic order to see the relations between them.

Let me know if this makes sense. :-)

[JohnCremona]

comment:4

It makes perfect sense -- I am very happy to see all this being implemented (or at least some of it), and not by me!

[mkoeppe]

comment:5

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[sagetrac-git]

Changed commit from 64865d2 to a9b8ecc

[sagetrac-git]

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

c00beb1	Merge tag '9.5.rc0' into public/scalar_elliptic_curve_endomorphisms
131930f	Merge tag '9.5.rc3' into public/scalar_elliptic_curve_endomorphisms
a9b8ecc	move .is_separable() to child classes

[sagetrac-git]

Changed commit from a9b8ecc to 83809df

[sagetrac-git]

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

253cd33	use {identity,negation}_morphism() throughout
83809df	fix :: in doctest

[sagetrac-git]

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

059d072

remove unused import

[sagetrac-git]

Changed commit from 83809df to 059d072

[sagetrac-git]

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

ba8ea21

Merge tag '9.6.beta2' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

Changed commit from 059d072 to ba8ea21

[sagetrac-git]

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

7ecae63	Merge tag '9.6.beta7' into public/scalar_elliptic_curve_endomorphisms
48afa78	Merge tag '9.6.rc1' into public/scalar_elliptic_curve_endomorphisms
38b8626	Merge tag '9.6' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

Changed commit from ba8ea21 to 38b8626

[sagetrac-git]

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

e7e02b1	Merge tag '9.7.rc0' into public/scalar_elliptic_curve_endomorphisms
61cabd5	Merge tag '9.7' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

Changed commit from fdc478e to 61cabd5

[sagetrac-git]

Changed commit from 61cabd5 to 80eb9b5

[sagetrac-git]

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

80eb9b5

Merge tag '9.8.beta2' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

Changed commit from 80eb9b5 to be6aedc

[sagetrac-git]

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

230019e	make linter happier
be6aedc	fix doctest failures

[sagetrac-git]

Changed commit from be6aedc to 5b403ad

[sagetrac-git]

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

5b403ad

Merge tag '9.8.beta3' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

Changed commit from 5b403ad to 9045e7d

[sagetrac-git]

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

9045e7d

Merge tag '9.8.beta5' into public/scalar_elliptic_curve_endomorphisms

[sagetrac-git]

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

79ae468

less experimental; deprecate .multiplication_by_m_isogeny()

[sagetrac-git]

Changed commit from 9045e7d to 79ae468

[yyyyx4]

comment:24

I've been constantly rebasing this branch for more than a year now — not trying to be annoying, but is there a chance we could finally get it merged?

I'd like to build more functionality on top of this (and #33915), but dragging around a bunch of unmerged tickets as dependencies slows down any development effort considerably.

[JohnCremona]

comment:25

I see that I looked at this in some detail a year ago, so I will do so again.

[JohnCremona]

comment:26

Some minor (and quick) suggestions, as this looks very good.

In the scaling_factor() method you return self._m which is an integer (in ZZ), but I think you should coerce it into the base field.

Having done this you can simplify is_separable() and is_injective() to a check that scaling_factor() is nonzero. For this reason it might be a good idea to store the image of m in the base field as well as m itself, on construction.

Do this and you'll get a positive review!

[sagetrac-git]

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

884263e

convert scaling factor to base ring

[sagetrac-git]

Changed commit from 79ae468 to 884263e

[JohnCremona]

Reviewer: John Cremona

[yyyyx4]

comment:30

Thanks a lot for reviewing this (indeed rather long) patch!

Replying to John Cremona:

In the scaling_factor() method you return self._m which is an integer (in ZZ), but I think you should coerce it into the base field.

Indeed, well spotted.

Having done this you can simplify is_separable() and is_injective() to a check that scaling_factor() is nonzero.

I agree for .is_separable(), but it seems that .is_injective() is not expressible in terms of the scaling factor alone: For supersingular curves [p] is purely inseparable (i.e., injective), but [kp] has nontrivial kernel whenever k>1 is not a power of p, while of course every multiple of [p] has the same scaling factor 0. So I kept the previous implementation of .is_injective().

[JohnCremona]

comment:31

You are right, of course. When we have separable_degree() and inseparable_degree() we can just return separable_degree()==1 for is_injective(), since the size of the kernel (over the algebraic closure and not meaning the fancy scheme-theoretic kernel!) is the separable degree.

[vbraun]

Changed branch from public/scalar_elliptic_curve_endomorphisms to 884263e