Florian Heigl ; Clemens Heuberger
-
Analysis of Digital Expansions of Minimal Weight
dmtcs:3009 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
-
https://doi.org/10.46298/dmtcs.3009
Analysis of Digital Expansions of Minimal Weight
Authors: Florian Heigl ; Clemens Heuberger
NULL##NULL
Florian Heigl;Clemens Heuberger
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.
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Heuberger, Clemens; Kropf, Sara; Wagner, Stephan, 2015, Variances And Covariances In The Central Limit Theorem For The Output Of A Transducer, European Journal Of Combinatorics, 49, pp. 167-187, 10.1016/j.ejc.2015.03.004, https://doi.org/10.1016/j.ejc.2015.03.004.
Imai, Hiroshi; Suppakitpaisarn, Vorapong, 2015, Improving Width-3 Joint Sparse Form To Attain Asymptotically Optimal Complexity On Average Case, Ieice Transactions On Fundamentals Of Electronics, Communications And Computer Sciences, E98.A, 6, pp. 1216-1222, 10.1587/transfun.e98.a.1216.