Welcome to the resource topic for
**2008/135**

**Title:**

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

**Authors:**
Clemens Heuberger, 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.

**ePrint:**
https://eprint.iacr.org/2008/135

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .