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.
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.399-412, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01197230
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:50
Dernière modification le : lundi 16 octobre 2017 - 11:18:04
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:33:49

Fichier

dmAQ0131.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01197230, version 1

Collections

Citation

Florian Heigl, Clemens Heuberger. Analysis of Digital Expansions of Minimal Weight. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.399-412, 2012, DMTCS Proceedings. 〈hal-01197230〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

110