CryptoDB
Minimal Weight and Colexicographically Minimal Integer Representations
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2006-21702,
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
}