Opened 13 years ago

Closed 13 years ago

#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: Hamish Ivey-Law Owned by: Hamish Ivey-Law
Priority: minor Milestone: sage-4.1.1
Component: performance Keywords: formal group elliptic curve
Cc: Merged in: Sage 4.1.1.alpha1
Authors: Hamish Ivey-Law, Tom Boothby Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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 (2)

trac_6407_added_double-and-add_algo_to_EllipticCurveFormalGroup.patch (2.8 KB) - added by Hamish Ivey-Law 13 years ago.
6407_part2.patch (1.1 KB) - added by Kelly Boothby 13 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 13 years ago by Hamish Ivey-Law

Status: newassigned

comment:2 Changed 13 years ago by Hamish Ivey-Law

Summary: Multiplication-by-n method on elliptic curve formal groups should use the double-and-add algorithm[with patch, needs review] Multiplication-by-n method on elliptic curve formal groups should use the double-and-add algorithm

Changed 13 years ago by Kelly Boothby

Attachment: 6407_part2.patch added

comment:3 Changed 13 years ago by Kelly Boothby

hlaw's implementation of the double-and-add algorithm resulted in a wasted doubling at the end -- potentially expensive. My part2 patch is a slight improvement.

comment:4 Changed 13 years ago by Robert Miller

Summary: [with patch, needs review] Multiplication-by-n method on elliptic curve formal groups should use the double-and-add algorithm[with patch, positive review] Multiplication-by-n method on elliptic curve formal groups should use the double-and-add algorithm

Looks good to me.

comment:5 Changed 13 years ago by Minh Van Nguyen

Authors: Hamish Ivey-Law, Tom Boothby
Reviewers: Robert Miller

comment:6 Changed 13 years ago by Minh Van Nguyen

Merged in: Sage 4.1.1.alpha1
Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.