Opened 5 years ago

Last modified 4 years ago

#22161 needs_work enhancement

Speedup of EllipticCurveIsogeny

Reported by: klui Owned by:
Priority: major Milestone: sage-8.0
Component: elliptic curves Keywords: elliptic curve
Cc: cremona Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/klui/speedup_of_ellipticcurveisogeny (Commits, GitHub, GitLab) Commit: 632679c4e666e0a2403f38941bb7aa8b64926117
Dependencies: Stopgaps:

Status badges

Description (last modified by klui)

When given a list of elements generating the kernel, EllipticCurveIsogeny computes the kernel by first computing the order of each generator. This could be slow since computing the order involves factoring integers.

Since EllipticCurveIsogeny takes the degree of the isogeny as an argument, we can use this to bound the kernel when the degree of the isogeny is known.

Change History (5)

comment:1 Changed 4 years ago by klui

  • Branch set to u/klui/speedup_of_ellipticcurveisogeny

comment:2 Changed 4 years ago by klui

  • Commit set to 632679c4e666e0a2403f38941bb7aa8b64926117
  • Description modified (diff)

New commits:

632679cUsing the degree of the isogeny as a bound for the kernel to avoid computing the order

comment:3 Changed 4 years ago by chapoton

  • Cc cremona added
  • Milestone changed from sage-7.5 to sage-8.0

comment:4 Changed 4 years ago by chapoton

  • Keywords removed
  • Status changed from new to needs_review

comment:5 Changed 4 years ago by cremona

  • Status changed from needs_review to needs_work

You are trying to avoid computing the group order I think, and I assume that the use case is large finite fields? I think that a better solution would be to change the order method of points to allow an optional multiple of the order to be passed together with its prime factors. Here the isogeny degree would be passed. This would be more generally useful.

Either way you should add a doctest illustrating the speedup, or explain why you do not.

Note: See TracTickets for help on using tickets.