A general expansion method using efficient endomorphisms

There are various expansion methods to accelerate scalar multiplication on special types of elliptic curves. In this paper we present a general expansion method that uses efficient endomorphisms. We first show that the set of all endomorphisms over a non-supersingular elliptic curve E is isomorphic to ℤ[ω] = {a + bω | a, b ∈ ℤ}, where ω is an algebraic integer with the smallest norm in an imaginary quadratic field, if ω is an endomorphism over E. Then we present a new division algorithm in ℤ[ω], by which an integer k can be expanded by the Frobenius endomorphism and ω. If ω is more efficient than a point doubling, we can use it to improve the performance of scalar multiplication by replacing some point doublings with the w maps. As an instance of this general method, we give a new expansion method using the efficiently computable endomorphisms used by Ciet et al. [1].