International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Some Explicit Formulae of NAF and its Left-to-Right Analogue

Authors:
Dong-Guk Han
Tetsuya Izu
Tsuyoshi Takagi
Download:
URL: http://eprint.iacr.org/2005/384
Search ePrint
Search Google
Abstract: Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run length appeared in FAN is asymptotically 16/7, which is longer than that of the standard NAF. We also apply the proposed formulae to the speed estimation of elliptic curve cryptosystems.
BibTeX
@misc{eprint-2005-12718,
  title={Some Explicit Formulae of NAF and its Left-to-Right Analogue},
  booktitle={IACR Eprint archive},
  keywords={foundations / signed binary representation,non-adjacent form, Hamming weight, zero-run length},
  url={http://eprint.iacr.org/2005/384},
  note={ christa@fun.ac.jp 13084 received 23 Oct 2005, last revised 28 Oct 2005},
  author={Dong-Guk Han and Tetsuya Izu and Tsuyoshi Takagi},
  year=2005
}