Cryptology ePrint Archive: Report 2005/420
Efficient Scalar Multiplication by Isogeny Decompositions
Christophe Doche and Thomas Icart and 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.
Category / Keywords: public-key cryptography / elliptic curve cryptosystem
Date: received 21 Nov 2005, last revised 22 Nov 2005
Contact author: doche at ics mq edu au
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20051123:064010 (All versions of this report)
Short URL: ia.cr/2005/420
[ Cryptology ePrint archive ]