Analysis of the Binary Asymmetric Joint Sparse Form

DOI10.1017/S0963548314000352MaRDI QIDQ2929859OpenAlexarXivFDO

Authors Clemens Heuberger, Sara Kropf

Publication date 14 November 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.2819

zbMATH Keywords

fluctuation functionHamming weightnon-adjacent formredundant digital expansionstransducer

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Cryptography (94A60)

Abstract: We consider redundant binary joint digital expansions of integer vectors. The redundancy is used to minimize the Hamming weight, i.e., the number of nonzero digit vectors. This leads to efficient linear combination algorithms in abelian groups, which are for instance used in elliptic curve cryptography. If the digit set is a set of contiguous integers containing the zero, a special syntactical condition is known to minimize the weight. We analyze 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.

Recommendations

• Analysis of linear combination algorithms in cryptography
• Applied Cryptography and Network Security
• Signed bits and fast exponentiation
• Low-weight JSF\(_3\) representations for pairs of integers
• Distribution results for low-weight binary representations for pairs of integers
• Algorithmic Number Theory
• Optimal random coding
• Analysis of digital expansions of minimal weight
• Digit Set Randomization in Elliptic Curve Cryptography
• Variances and covariances in the central limit theorem for the output of a transducer

Cites work

• DISTRIBUTION OF BINOMIAL COEFFICIENTS AND DIGITAL FUNCTIONS
• Distribution results for low-weight binary representations for pairs of integers
• Mellin transforms and asymptotics: Digital sums
• On the sum of digits functions for number systems with negative bases
• Some extremal functions in Fourier analysis

Cited in

(10)

• Output sum of transducers: limiting distribution and periodic fluctuation
• Variances and covariances in the central limit theorem for the output of a transducer
• Calculating average joint Hamming weight for minimal weight conversion of d integers
• Analysis of linear combination algorithms in cryptography
• Counting optimal joint digit expansions
• On q-quasiadditive and q-quasimultiplicative functions
• Minimal weight and colexicographically minimal integer representations
• Low-weight JSF\(_3\) representations for pairs of integers
• scientific article; zbMATH DE number 7650128 (Why is no real title available?)
• The Hamming weight of the non-adjacent-form under various input statistics

This page was built for publication: Analysis of the Binary Asymmetric Joint Sparse Form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929859)