Efficient scalar multiplication by isogeny decompositions

On an elliptic curve, the degree of an isogeny corresponds essentially to the degrees of the polynomial expressions involved in its application. The multiplication-by-ℓ map [ℓ] has degree, therefore the complexity to directly evaluate [ℓ](P) is O(ℓ²). For a small prime ℓ (= 2, 3) such that the additive binary representation provides no better performance, this represents the true cost of application of scalar multiplication. If an elliptic curve admits an isogeny φ of degree ℓ then the costs of computing φ(P) should in contrast be O(ℓ) field operations. Since we then have a product expression [ℓ] = φ̂φ, the existence of an ℓ-isogeny φ on an elliptic curve yields a theoretical improvement from O(ℓ²) to O(ℓ) field operations for the evaluation of [ℓ](P) by naïve application of the defining polynomials. In this work we investigate actual improvements for small ℓ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition [ℓ] = φ̂φ, and provide explicit examples of such a family of curves with simple decomposition for [3]. Finally we derive a new tripling algorithm to find complexity improvements to triplication on a curve in certain projective coordinate systems, then combine this new operation to non-adjacent forms for ℓ-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.