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 radix2 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 lefttoright (\ie from mostsignificant to leastsignificant). The output representation is optimal in the sense that, of all radix2 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
 20080331: received
 Short URL
 https://ia.cr/2008/135
 License

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} }