On the zero-run length of a signed binary representation

概要

論文の詳細を見る
MI: Global COE Program Education-and-Research Hub for Mathematics-for-IndustryグローバルCOEプログラム「マス･フォア･インダストリ教育研究拠点」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.
2009-04-08