An Efficient Algorithm for Elliptic Curve Scalar Multiplication Using Extended Double-Base Chain and Point Halving

Abstract

We propose to represent a scalar in the form of d (1/2)(superscript a)3(superscript b), where a and b are integers and d is an odd integer belonging to a given set. This representation is a combination of the extended double-base number system (DBNS) and the double-base chain representation using powers of 1/2 and 3. Experimental results show that our approach leads to a shorter DBNS expansion and a lower complexity in elliptic curve scalar multiplication, with the cost of only a few pre-computations and storages. This contributes to the efficient implementation of elliptic curve cryptography (ECC).