**Minimal Weight and Colexicographically Minimal Integer Representations**

*Clemens Heuberger and 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.

**Category / Keywords: **implementation / redundant number systems, joint representations, minimal weight, colexicographic order, Joint Sparse Form.

**Date: **received 22 Jun 2006

**Contact author: **jamuir at scs carleton ca

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20060626:175328 (All versions of this report)

**Short URL: **ia.cr/2006/209

[ Cryptology ePrint archive ]