Skip to content

multiplication_by_m_isogeny is only correct up to automorphism #32490

Closed

Description

@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

Activity

  1. added this to the sage-9.5 milestone on Sep 8, 2021
  2. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    Author
  3. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    MemberAuthor

    New commits:

    2d1c955make sure multiplication_by_m_isogeny picks the correct isomorphism
  4. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    MemberAuthor
  5. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    MemberAuthor

    Commit: 2d1c955

  6. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    MemberAuthor

    Stopgaps: mathematically_wrong

  7. yyyyx4 commented on Sep 8, 2021

    @yyyyx4
    MemberAuthor

    Author: Lorenz Panny

  8. changed the title [-]sign errors in multiplication_by_m_isogeny[/-] [+]multiplication_by_m_isogeny is only correct up to automorphism[/+] on Sep 8, 2021
  9. tscrim commented on Sep 13, 2021

    @tscrim
    Collaborator
    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.

  10. yyyyx4 commented on Sep 13, 2021

    @yyyyx4
    MemberAuthor
    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.

  11. tscrim commented on Sep 13, 2021

    @tscrim
    Collaborator

    Changed stopgaps from mathematically_wrong to none

  12. 6 remaining items

  13. sagetrac-git commented on Sep 17, 2021

    sagetrac-gitmannequin
    Mannequin

    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 doctests
    c24d57fRevert "hack to make * compose isogenies and isomorphisms correctly"
    5714eaamake * compose isogenies and isomorphisms correctly
    b2d61b8make patchbot plugins happier
    bb8c235return NotImplemented instead of raising NotImplementedError
    207d534add EllipticCurveHom to documentation
    c6b8f66feedback from #32388: inline _switch_sign()
    fdc6117#32388: more doctests
    40081c7not necessary
    ead071dmake sure multiplication_by_m_isogeny picks the correct isomorphism
  14. sagetrac-git commented on Sep 17, 2021

    sagetrac-gitmannequin
    Mannequin

    Changed commit from 2d1c955 to ead071d

  15. yyyyx4 commented on Sep 17, 2021

    @yyyyx4
    MemberAuthor
    comment:9

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

  16. yyyyx4 commented on Sep 17, 2021

    @yyyyx4
    MemberAuthor

    Dependencies: #32388

  17. tscrim commented on Sep 21, 2021

    @tscrim
    Collaborator
    comment:10

    LGTM. Thanks.

  18. yyyyx4 commented on Oct 23, 2021

    @yyyyx4
    MemberAuthor
    comment:11

    Bumping priority since this bug can lead to mathematical errors.

  19. vbraun commented on Oct 23, 2021

    @vbraun
    Member
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions