Welcome to the resource topic for 2006/209
Title:
Minimal Weight and Colexicographically Minimal Integer Representations
Authors: Clemens Heuberger, James A. Muir
Abstract:Redundant number systems (e.g. signed binary representations) have been utilized to efficiently implement algebraic operations required by public-key cryptosystems, especially those based on elliptic curves. Several families of integer representations have been proposed that have a minimal number of nonzero digits (so-called \emph{minimal weight} representations). We observe that many of the constructions for minimal weight representations actually work by building representations which are minimal in another sense. For a given set of digits, these constructions build \emph{colexicographically minimal} representations; that is, they build representations where each nonzero digit is positioned as far left (toward the most significant digit) as possible. We utilize this strategy in a new algorithm which constructs a very general family of minimal weight dimension-d \emph{joint} representations for any d \geq 1. The digits we use are from the set \{a \in \ZZ: \ell \leq a \leq u\} where \ell \leq 0 and u \geq 1 are integers. By selecting particular values of \ell and u, it is easily seen that our algorithm generalizes many of the minimal weight representations previously described in the literature. From our algorithm, we obtain a syntactical description of a particular family of dimension-d joint representations; any representation which obeys this syntax must be both colexicographically minimal and have minimal weight; moreover, every vector of integers has exactly one representation that satisfies this syntax. We utilize this syntax in a combinatorial analysis of the weight of the representations.
ePrint: https://eprint.iacr.org/2006/209
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 .