# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [13 references]

https://hal.inria.fr/hal-01197230
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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

### File

dmAQ0131.pdf
Publisher files allowed on an open archive

### Citation

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, ⟨10.46298/dmtcs.3009⟩. ⟨hal-01197230⟩

Record views