Paper 2005/384

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

Dong-Guk Han, Tetsuya Izu, and Tsuyoshi Takagi

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
signed binary representationnon-adjacent formHamming weightzero-run length
Contact author(s)
christa @ fun ac jp
History
2005-10-28: revised
2005-10-24: received
See all versions
Short URL
https://ia.cr/2005/384
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/384,
      author = {Dong-Guk Han and Tetsuya Izu and Tsuyoshi Takagi},
      title = {Some Explicit Formulae of NAF and its Left-to-Right Analogue},
      howpublished = {Cryptology ePrint Archive, Paper 2005/384},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/384}},
      url = {https://eprint.iacr.org/2005/384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.