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

https://hal.inria.fr/hal-01197230
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

File

dmAQ0131.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01197230, version 1

Collections

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. ⟨hal-01197230⟩

Share

Metrics

Record views

339

Files downloads

574