Analysis of the Binary Asymmetric Joint Sparse Form. (November 2014)

• Record Type: Journal Article
• Authors: HEUBERGER, CLEMENS; KROPF, SARA; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 6(2014:Nov.)
• Page Start: 1087
• Page End: 1113
• Publication Date: 2014-11
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000352
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>We consider redundant binary joint digital expansions of integer vectors. The redundancy is used to minimize the Hamming weight, <italic>i.e.</italic>, 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.</p> <p>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 <italic>N</italic>. 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.</p> </abstract>