Two efficient algorithms for arithmetic of elliptic curves using Frobenius map

In this paper, we present two ecient algorithms computing scalar multiplications of a point in an elliptic curve deÞned over a small Þnite Þeld, the Frobenius map of which has small trace. Both methods use the identity which expresses multiplication-by-m maps by polynomials of Frobenius maps. Both are applicable for a large family of elliptic curves and more ecient than any other methods applicable for the family. More precisely, by Algorithm 1(Frobenius k-ary method), we can com- pute mP in at most 2l=5+28 elliptic additions for arbitrary l bit integer m and a point P on some elliptic curves. For other curves, the number of elliptic additions required is less than l. Algorithm 2(window method) requires at average 2l=3 elliptic additions to compute mP for l bit integer m and a point P on a family of elliptic curves. For some 'good' elliptic curves, it requires 5l=12 + 11 elliptic additions at average.