{"docId":3009,"paperId":3009,"url":"https:\/\/dmtcs.episciences.org\/3009","doi":"10.46298\/dmtcs.3009","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":262,"name":"DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)"}],"section":[{"sid":66,"title":"Proceedings","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01197230","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-01197230v1","dateSubmitted":"2017-01-31 10:22:08","dateAccepted":null,"datePublished":"2012-01-01 00:00:00","titles":{"en":"Analysis of Digital Expansions of Minimal Weight"},"authors":["Heigl, Florian","Heuberger, Clemens"],"abstracts":{"en":"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":[["dynamic programming"],["limit distribution"],["digital expansions"],["Hamming weight"],["elliptic curve cryptography"],["Frobenius endomorphism"],["minimal expansions"],"[INFO.INFO-DS] Computer Science [cs]\/Data Structures and Algorithms [cs.DS]","[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]","[MATH.MATH-CO] Mathematics [math]\/Combinatorics [math.CO]","[INFO.INFO-CG] Computer Science [cs]\/Computational Geometry [cs.CG]"]}