Dr Christophe Doche
Macquarie University
Title: Efficient Scalar Multiplication by Isogeny Decompositions (joint work with David Kohel and Thomas Icart)
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 curve 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\"ive
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.