10.46298/dmtcs.3009
https://dmtcs.episciences.org/3009
Heigl, Florian
Florian
Heigl
Heuberger, Clemens
Clemens
Heuberger
Analysis of Digital Expansions of Minimal Weight
Extending an idea of Suppakitpaisarn, Edahiro and Imai, a dynamic programming approach for computing digital expansions of minimal weight is transformed into an asymptotic analysis of minimal weight expansions. The minimal weight of an optimal expansion of a random input of length $\ell$ is shown to be asymptotically normally distributed under suitable conditions. After discussing the general framework, we focus on expansions to the base of $\tau$, where $\tau$ is a root of the polynomial $X^2- \mu X + 2$ for $\mu \in \{ \pm 1\}$. As the Frobenius endomorphism on a binary Koblitz curve fulfils the same equation, digit expansions to the base of this $\tau$ can be used for scalar multiplication and linear combination in elliptic curve cryptosystems over these curves.
episciences.org
dynamic programming
limit distribution
digital expansions
Hamming weight
elliptic curve cryptography
Frobenius endomorphism
minimal expansions
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
2023-03-28
2012-01-01
2012-01-01
en
journal article
https://hal.science/hal-01197230v1
1365-8050
https://dmtcs.episciences.org/3009/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Proceedings
Researchers
Students