### 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.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
redundant number systemsminimal weight
Contact author(s)
jamuir @ cs smu ca
History
Short URL
https://ia.cr/2008/135

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.