You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
multiplication_by_m_isogeny is only correct up to automorphism #32490
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.
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.
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.
Activity
yyyyx4 commentedon Sep 8, 2021
yyyyx4 commentedon Sep 8, 2021
New commits:
2d1c955make sure multiplication_by_m_isogeny picks the correct isomorphismyyyyx4 commentedon Sep 8, 2021
Branch: public/pick_correct_isomorphism_in_multiplication_by_m_isogeny
yyyyx4 commentedon Sep 8, 2021
Commit:
2d1c955yyyyx4 commentedon Sep 8, 2021
Stopgaps: mathematically_wrong
yyyyx4 commentedon Sep 8, 2021
Author: Lorenz Panny
[-]sign errors in multiplication_by_m_isogeny[/-][+]multiplication_by_m_isogeny is only correct up to automorphism[/+]tscrim commentedon Sep 13, 2021
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 commentedon Sep 13, 2021
Replying to @tscrim:
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
EllipticCurveHomlater.tscrim commentedon Sep 13, 2021
Changed stopgaps from mathematically_wrong to none
6 remaining items
sagetrac-git commentedon Sep 17, 2021
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:
69a15a2reflect deprecation of mutable isogenies in doctestsc24d57fRevert "hack to make * compose isogenies and isomorphisms correctly"5714eaamake * compose isogenies and isomorphisms correctlyb2d61b8make patchbot plugins happierbb8c235return NotImplemented instead of raising NotImplementedError207d534add EllipticCurveHom to documentationc6b8f66feedback from #32388: inline _switch_sign()fdc6117#32388: more doctests40081c7not necessaryead071dmake sure multiplication_by_m_isogeny picks the correct isomorphismsagetrac-git commentedon Sep 17, 2021
Changed commit from
2d1c955toead071dyyyyx4 commentedon Sep 17, 2021
Rebased and adapted to the new syntax. (Only the last commit is relevant here; the rest are from #32388.)
yyyyx4 commentedon Sep 17, 2021
Dependencies: #32388
tscrim commentedon Sep 21, 2021
LGTM. Thanks.
yyyyx4 commentedon Oct 23, 2021
Bumping priority since this bug can lead to mathematical errors.
vbraun commentedon Oct 23, 2021
Changed branch from public/pick_correct_isomorphism_in_multiplication_by_m_isogeny to
ead071d