DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

Analysis of Digital Expansions of Minimal Weight

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 ℓ 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

Valid XHTML 1.0 Transitional