Efficient Scalar Multiplication by Isogeny Decompositions.
Christophe Doche, Thomas Icart, David Kohel · 2005
Abstract. 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 ℓ 2, therefore the complexity to directly evaluate [ℓ](P) isO(ℓ 2). 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(ℓ)fieldoperations. Since we then have a product expression [ℓ] =ˆϕϕ, the existence of an ℓ-isogeny ϕ on an elliptic curve yields a theoretical improvement from O(ℓ 2)toO(ℓ) field operations for the evaluation of [ℓ](P) bynaï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.