Ticket #6407 (closed enhancement: fixed)
[with patch, positive review] Multiplication-by-n method on elliptic curve formal groups should use the double-and-add algorithm
| Reported by: | hlaw | Owned by: | hlaw |
|---|---|---|---|
| Priority: | minor | Milestone: | sage-4.1.1 |
| Component: | performance | Keywords: | formal group elliptic curve |
| Cc: | Author(s): | Hamish Ivey-Law, Tom Boothby | |
| Report Upstream: | Reviewer(s): | Robert Miller | |
| Merged in: | Sage 4.1.1.alpha1 | Work issues: |
Description
Currently EllipticCurveFormalGroup.mult_by_n() is implemented simply by applying the group law to itself n times (except when working over a field of characteristic zero, in which case a fast algorithm is used). This linear algorithm should be replaced with the logarithmic double-and-add algorithm (i.e. the additive version of the standard square-and-multiply algorithm).
Attachments
-
trac_6407_added_double-and-add_algo_to_EllipticCurveFormalGroup.patch
(2.8 KB) - added by hlaw
7 months ago.
-
6407_part2.patch
(1.1 KB) - added by boothby
7 months ago.
Change History
Note: See
TracTickets for help on using
tickets.
