Analysis of the Binary Asymmetric Joint Sparse Form. (November 2014) - HEUBERGER, CLEMENS; KROPF, SARA; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
<x content-type="archive" xml:space="preserve">Abstract</x> We consider redundant binary joint digital expansions of integer vectors. The redundancy is used to minimize the Hamming weight, i.e., the number of non-zero digit vectors. This leads to efficient linear combination algorithms in abelian groups, which are used in elliptic curve cryptography, for instance. If the digit set is a set of contiguous integers containing zero, a special syntactical condition is known to minimize the weight. We analyse the optimal weight of all non-negative integer vectors with maximum entry less than N. The expectation and the variance are given with a main term and a periodic fluctuation in the second-order term. Finally, we prove asymptotic normality.