IACR paper details
Title  Minimal Weight and Colexicographically Minimal Integer Representations 

Booktitle  IACR Eprint archive 

Pages  

Year  2006 

URL  http://eprint.iacr.org/2006/209 

Author  Clemens Heuberger 

Author  James A. Muir 

Abstract 
Redundant number systems (e.g. signed binary representations) have
been utilized to efficiently implement algebraic operations required
by publickey cryptosystems, especially those based on elliptic
curves. Several families of integer representations have been
proposed that have a minimal number of nonzero digits (socalled
\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.


Search for the paper
@misc{eprint200621702,
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.},
url={http://eprint.iacr.org/2006/209},
note={ jamuir@scs.carleton.ca 13321 received 22 Jun 2006},
author={Clemens Heuberger and James A. Muir},
year=2006
}
Download a complete BibTeX file.