[with patch, positive review] Multiplicationbyn method on elliptic curve formal groups should use the doubleandadd algorithm
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 doubleandadd algorithm (i.e. the additive version of the standard squareandmultiply algorithm).
Change History (8)
Summary: 
Multiplicationbyn method on elliptic curve formal groups should use the doubleandadd algorithm →
[with patch, needs review] Multiplicationbyn method on elliptic curve formal groups should use the doubleandadd algorithm

Summary: 
[with patch, needs review] Multiplicationbyn method on elliptic curve formal groups should use the doubleandadd algorithm →
[with patch, positive review] Multiplicationbyn method on elliptic curve formal groups should use the doubleandadd algorithm

Authors: 
→ Hamish IveyLaw, Tom Boothby

Reviewers: 
→ Robert Miller

Merged in: 
→ Sage 4.1.1.alpha1

Resolution: 
→ fixed

Status: 
assigned →
closed

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