Opened 13 years ago

Closed 13 years ago

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

Reported by: Owned by: Hamish Ivey-Law Hamish Ivey-Law minor sage-4.1.1 performance formal group elliptic curve Sage 4.1.1.alpha1 Hamish Ivey-Law, Tom Boothby Robert Miller N/A

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).

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

Status: new → assigned

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

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 → Robert Miller

comment:6 Changed 13 years ago by Minh Van Nguyen

Merged in: → Sage 4.1.1.alpha1 → fixed assigned → closed
Note: See TracTickets for help on using tickets.