Editorial Board

JMI2009A-4 On the zero-run length of a signed binary representation (pp.27-32)

Author(s): Hisashi Yamada, Tsuyoshi Takagi and Kouichi Sakurai

J. Math-for-Ind. 1A (2009) 27-32.

Abstract
Elliptic curve cryptosystems (ECC) are suitable for memory-constraint devices like smart cards due to their small key-size. Non-adjacent form (NAF) is a signed binary representation of integers used for implementing ECC. Recently, Schmidt-Samoa et al. proposed the fractional $w$MOF (Frac-$w$MOF), which is a left-to-right analogue of NAF, where $w$ is the fractional window size $w=w_{0}+w_{1}$ of integer $w_{0}$ and fractional number $w_{1}$. On the contrary to NAF, there are some consecutive none-zero bits in Frac-$w$MOF, and thus the zero-run length of the Frac-$w$MOF is not equal to that of the variants of NAF. In this paper we present an asymptotic formula of zero-run length of Frac-$w$MOF. Indeed, the average zero-run length of the Frac-$w$MOF is asymptotically $w\frac{2^{w_{0}+1}}{2^{w_{0}+1}-1}$, which is longer than that of the fractional $w$NAF.

Keyword(s).  elliptic curve cryptosystem, signed binary representations, zero-run length