International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Minimal Weight and Colexicographically Minimal Integer Representations

Clemens Heuberger
James A. Muir
Search ePrint
Search Google
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.
  title={Minimal Weight and Colexicographically Minimal Integer Representations},
  booktitle={IACR Eprint archive},
  keywords={implementation / redundant number systems, joint representations, minimal weight, colexicographic order, Joint Sparse Form.},
  note={ 13321 received 22 Jun 2006},
  author={Clemens Heuberger and James A. Muir},