Skip to Main content Skip to Navigation
Conference papers

Analysis of Digital Expansions of Minimal Weight

Abstract : 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:54:50 PM
Last modification on : Monday, October 16, 2017 - 11:18:04 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:33:49 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01197230, version 1



Florian Heigl, Clemens Heuberger. Analysis of Digital Expansions of Minimal Weight. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.399-412. ⟨hal-01197230⟩



Record views


Files downloads