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: |
Description (last modified by )
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
- Branch set to u/klui/speedup_of_ellipticcurveisogeny
comment:2 Changed 4 years ago by
- Commit set to 632679c4e666e0a2403f38941bb7aa8b64926117
- Description modified (diff)
comment:3 Changed 4 years ago by
- Cc cremona added
- Milestone changed from sage-7.5 to sage-8.0
comment:4 Changed 4 years ago by
- Keywords removed
- Status changed from new to needs_review
comment:5 Changed 4 years ago by
- 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.
New commits:
Using the degree of the isogeny as a bound for the kernel to avoid computing the order