### Analysis of Digital Expansions of Minimal Weight

*Florian Heigl, Clemens Heuberger*

#### 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 ℓ is shown to be asymptotically normally distributed under suitable conditions. After discussing the general framework, we focus on expansions to the base of τ, where τ is a root of the polynomial X2-µX+2 for µ∈{±1}. As the Frobenius endomorphism on a binary Koblitz curve fulfils the same equation, digit expansions to the base of this τ can be used for scalar multiplication and linear combination in elliptic curve cryptosystems over these curves.

Full Text: PostScript PDF