### 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.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
redundant number systemsjoint representationsminimal weightcolexicographic orderJoint Sparse Form.
Contact author(s)
jamuir @ scs carleton ca
History
Short URL
https://ia.cr/2006/209

CC BY

BibTeX

@misc{cryptoeprint:2006/209,
author = {Clemens Heuberger and James A.  Muir},
title = {Minimal Weight and Colexicographically Minimal Integer Representations},
howpublished = {Cryptology ePrint Archive, Paper 2006/209},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/209}},
url = {https://eprint.iacr.org/2006/209}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.