Minimal weight and colexicographically minimal integer representations

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 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 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 joint representations for any d ≥ 1. The digits we use are from the set {a ∈ Z : l ≤ a ≤ u} where l ≤ 0 and u ≥ 1 are integers. By selecting particular values of l 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.

Keywords

• redundant number systems
• signed digits
• integer representations
• joint representations
• minimal weight
• colexicographic order
• joint sparse form