Welcome to the resource topic for
**2005/420**

**Title:**

Efficient Scalar Multiplication by Isogeny Decompositions

**Authors:**
Christophe Doche, Thomas Icart, David R. Kohel

**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–\ell map [\ell] has degree~\ell^2, therefore

the complexity to directly evaluate [\ell](P) is O(\ell^2).

For a small prime \ell\, (= 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 curves admits an isogeny \varphi of degree \ell then

the costs of computing \varphi(P) should in contrast be O(\ell) field

operations. Since we then have a product expression [\ell] =
\hat{\varphi}\varphi, the existence of an \ell-isogeny \varphi on

an elliptic curve yields a theoretical improvement from O(\ell^2) to

O(\ell) field operations for the evaluation of [\ell](P) by naïve

application of the defining polynomials. In this work we investigate

actual improvements for small \ell of this asymptotic complexity.

For this purpose, we describe the general construction of families of

curves with a suitable decomposition [\ell] = \hat{\varphi}\varphi,

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 \ell-adic expansions in order to obtain an improved

strategy for scalar multiplication on elliptic curves.

**ePrint:**
https://eprint.iacr.org/2005/420

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .