multiplication_by_m_isogeny is only correct up to automorphism

[yyyyx4]

This is wrong:

sage: E = EllipticCurve(QQbar, [1,0])
sage: E.multiplication_by_m_isogeny(1).rational_maps()
(x, -y)

sage: E = EllipticCurve(GF(127), [1,0])
sage: P = E.random_point()
sage: E.multiplication_by_m_isogeny(5)(P)
(15 : 56 : 1)
sage: 5*P
(15 : 71 : 1)
sage: -5*P
(15 : 56 : 1)
sage: E.multiplication_by_m(5) == (-E.multiplication_by_m_isogeny(5)).rational_maps()
True

It isn't consistently wrong:

sage: E = EllipticCurve(QQ, [1,0])
sage: E.multiplication_by_m_isogeny(1).rational_maps()
(x, y)

---

The trouble is that the method first constructs an isogeny with the correct kernel and codomain, then sets the precomputed rational maps. However, the isomorphism to the prescribed codomain is not unique, and picking the wrong one means the resulting isogeny is off by an automorphism — most commonly [-1].

The patch is not pretty, but it seems to fix the issue for now and shouldn't cause any significant slowdowns.
Once (if) #32388 gets in, we should probably instead use an EllipticCurveHom subclass specifically for scalar multiplications that imitates a normal isogeny but with different internals. I do have a draft of this ready and it's not only much cleaner, but also resolves part of #8014.

Depends on #32388

CC: @JohnCremona @defeo

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: ead071d

Reviewer: Travis Scrimshaw

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

[yyyyx4]

New commits:

2d1c955

make sure multiplication_by_m_isogeny picks the correct isomorphism

[yyyyx4]

Branch: public/pick_correct_isomorphism_in_multiplication_by_m_isogeny

[yyyyx4]

Commit: 2d1c955

[yyyyx4]

Stopgaps: mathematically_wrong

[yyyyx4]

Author: Lorenz Panny

[tscrim]

comment:3

Based on your description, it seems like the thing to do would be to make #32388 a dependency since it generally seems to be better. You can then use this ticket as motivation for #32388 if that is necessary.

[yyyyx4]

comment:4

Replying to @tscrim:

Based on your description, it seems like the thing to do would be to make #32388 a dependency since it generally seems to be better.

I was worried that #32388 might take a while to get in, which could cause this (in principle, totally unrelated) bug to remain unfixed for no good reason if there was a dependency. Hence why I figured the best way to proceed would be to first apply this minimal bugfix and pursue the longer-term solution based on EllipticCurveHom later.

[tscrim]

Changed stopgaps from mathematically_wrong to none

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:5

Then let's get the bug-fix in.

[yyyyx4]

comment:6

Now that #32388 is also green, this will almost certainly cause test failures when both are merged (since this currently uses a method deprecated in #32388). What's the recommended way of dealing with this? Should I rebase this onto #32388 using the new syntax and add a dependency after all?

[tscrim]

comment:7

Sounds like you should make this depend on #32388.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. Last 10 new commits:

69a15a2	reflect deprecation of mutable isogenies in doctests
c24d57f	Revert "hack to make * compose isogenies and isomorphisms correctly"
5714eaa	make * compose isogenies and isomorphisms correctly
b2d61b8	make patchbot plugins happier
bb8c235	return NotImplemented instead of raising NotImplementedError
207d534	add EllipticCurveHom to documentation
c6b8f66	feedback from #32388: inline _switch_sign()
fdc6117	#32388: more doctests
40081c7	not necessary
ead071d	make sure multiplication_by_m_isogeny picks the correct isomorphism

[sagetrac-git]

Changed commit from 2d1c955 to ead071d

[yyyyx4]

comment:9

Rebased and adapted to the new syntax. (Only the last commit is relevant here; the rest are from #32388.)

[yyyyx4]

Dependencies: #32388

[tscrim]

comment:10

LGTM. Thanks.

[yyyyx4]

comment:11

Bumping priority since this bug can lead to mathematical errors.

[vbraun]

Changed branch from public/pick_correct_isomorphism_in_multiplication_by_m_isogeny to ead071d