Paper 2008/135

Unbalanced Digit Sets and the Closest Choice Strategy for Minimal Weight Integer Representations

Clemens Heuberger and James A. Muir

Abstract

An online algorithm is presented that produces an optimal radix-2 representation of an input integer $n$ using digits from the set $D_{\ell,u}=\{a\in\Z:\ell\le a\le u\}$, where $\ell \leq 0$ and $u \geq 1$. The algorithm works by scanning the digits of the binary representation of $n$ from left-to-right (\ie from most-significant to least-significant). The output representation is optimal in the sense that, of all radix-2 representations of $n$ with digits from $D_{\ell,u}$, it has as few nonzero digits as possible (\ie it has \emph{minimal weight}). Such representations are useful in the efficient implementation of elliptic curve cryptography. The strategy the algorithm utilizes is to choose an integer of the form $d 2^i$, where $d \in D_{\ell,u}$, that is closest to $n$ with respect to a particular distance function. It is possible to choose values of $\ell$ and $u$ so that the set $D_{\ell,u}$ is unbalanced in the sense that it contains more negative digits than positive digits, or more positive digits than negative digits. Our distance function takes the possible unbalanced nature of $D_{\ell,u}$ into account.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
redundant number systemsminimal weight
Contact author(s)
jamuir @ cs smu ca
History
2008-03-31: received
Short URL
https://ia.cr/2008/135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/135,
      author = {Clemens Heuberger and James A.  Muir},
      title = {Unbalanced Digit Sets and the Closest Choice Strategy for Minimal Weight Integer Representations},
      howpublished = {Cryptology ePrint Archive, Paper 2008/135},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/135}},
      url = {https://eprint.iacr.org/2008/135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.