Analysis of width-w non-adjacent forms to imaginary quadratic bases

详细信息    查看全文

• 作者：Clemens Heuberger<sup>1sup><sup> ; sup><sup>clemens.heuberger@tugraz.atsup> ; Daniel Krenn<sup> ; sup><sup>1sup><sup> ; sup><sup>math@danielkrenn.atsup><sup> ; sup><sup>krenn@math.tugraz.atsup>
• 关键词：¦Ó-adic expansions ; Non-adjacent forms ; Redundant digit sets ; Elliptic curve cryptography ; Koblitz curves ; Frobenius endomorphism ; Scalar multiplication ; Hamming weight ; Sum of digits ; Fractals ; Fundamental domain
• 刊名：Journal of Number Theory
• 出版年：2013
• 出版时间：May, 2013
• 年：2013
• 卷：133
• 期：5
• 页码：1752-1808
• 全文大小：808 K

文摘

We consider digital expansions to the base of an algebraic integer ¦Ó. For a , the set of admissible digits consists of 0 and one representative of every residue class modulo which is not divisible by ¦Ó. The resulting redundancy is avoided by imposing the width-w non-adjacency condition. Such constructs can be efficiently used in elliptic curve cryptography in conjunction with Koblitz curves. The present work deals with analysing the number of occurrences of a fixed non-zero digit. In the general setting, we study all w-NAFs of given length of the expansion (expectation, variance, central limit theorem). In the case of an imaginary quadratic ¦Ó and the digit set of minimal norm representatives, the analysis is much more refined. The proof follows Delange?s method. We also show that each element of has a w-NAF in that setting.