Explicit lower bound for the length of minimal weight τ -adic expansions on Koblitz curves

Elliptic curve cryptosystems (ECC) are emerging cryptographic standards which can be used instead of RSA cryptosystems, and are practically used. In ECC, scalar multiplication (or point multiplication) is the dominant operation, namely computing an integer multiple for a given integer and a point on an elliptic curve. However, for practical use, it is a very important matter to improve the efficiency of scalar multiplication. The τ -adic non-adjacent form (τ -NAF) proposed by Solinas, is one of the most efficient algorithms to compute scalar multiplications on Koblitz curves. Avanzi, Heuberger, and Prodinger have proven the minimality of the Hamming weight of the τ -NAF on Koblitz curves. However, the lower bound for the length of minimal Hamming weight τ -adic expansions is not known yet. In this paper, we shall derive an explicit lower bound for the length of minimal Hamming weight τ -adic expansions. We shall also give a new proof of the minimality of the Hamming weight of the τ -NAF on Koblitz curves. Further, by using the proof of the lower bound and the new proof of the minimality, we classify a minimal length τ -adic expansion with minimal Hamming weight except for two special cases. The classification shows that the τ -NAF has almost minimal length among all τ -adic expansions of minimal Hamming weight and we can easily convert the τ -NAF into a minimal length τ -adic expansion without changing the Hamming weight. This fact follows immediately from the proof of the lower bound and our new proof.