Improved algorithms for an efficient arithmetic on some categories of elliptic curves
Mustapha Hedabou · International Journal of Computational Complexity and Intelligent Algorithms · 2016
The Frobenius endomorphism τ is known to be useful for an efficient scalar multiplication on elliptic curves E(Fqm ) defined either over fields with small characteristics or over optimal extension fields.In this paper, we will present two techniques that aim to enhance the Frobenius-based methods for computing the scalar multiplication on these curves.The first method, called the generalised τ -adic method, is dedicated to improve the efficiency of the generalised τ -adic method when the elliptic curves are defined over fields of small characteristics.The generalised τ -adic with even digits improves substantially the computation time and the number of stored points whereas the generalised τ -adic with odd digits reduces only the number of stored points but it offers better resistance against the SPA attacks.The generalised τ -adic method is particularly efficient when the trace of the used curve is small.The second method allows to reduce by about 50% the number of the stored points by the Frobenius-based algorithm on elliptic curve defined over optimal extension fields.Finally, we show that there are a lot of curves which are well suited for cryptography, and for which the proposed methods can be applied.