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 .