@inproceedings{b51d0ea2a6d94228a6e6c88062b87908,

title = "Efficient scalar multiplication by isogeny decompositions",

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, therefore the complexity to directly evaluate [ℓ](P) is O(ℓ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(ℓ) field operations. Since we then have a product expression [ℓ] = {\^φ}φ, the existence of an ℓ-isogeny φ on an elliptic curve yields a theoretical improvement from O(ℓ2) to O(ℓ) field operations for the evaluation of [ℓ](P) by na{\"i}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.",

author = "Christophe Doche and Thomas Icart and Kohel, {David R.}",

year = "2006",

doi = "10.1007/11745853_13",

language = "English",

isbn = "3540338519",

volume = "3958 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "191--206",

editor = "Moti Yung and Yevgeniy Dodis and Aggelos Kiayias and Tal Malkin",

booktitle = "Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings",

address = "United States",

note = "9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 ; Conference date: 24-04-2006 Through 26-04-2006",

}