### Redundant $\tau$-adic Expansions II: Non-Optimality and Chaotic Behaviour

Clemens Heuberger

##### Abstract

When computing scalar multiples on Koblitz curves, the Frobenius endomorphism can be used to replace the usual doublings on the curve. This involves digital expansions of the scalar to the complex base $\tau=(\pm 1\pm \sqrt{-7})/2$ instead of binary expansions. As in the binary case, this method can be sped up by enlarging the set of valid digits at the cost of precomputing some points on the curve. In the binary case, it is known that a simple syntactical condition (the so-called $w$-NAF-condition) on the expansion ensures that the number of curve additions is minimised. The purpose of this paper is to show that this is not longer true for the base $\tau$ and $w\in\{4,5,6\}$. Even worse, it is shown that there is no longer an online algorithm to compute an optimal expansion from the digits of some standard expansion from the least to the most significant digit, which can be interpreted as chaotic behaviour. The proofs heavily depend on symbolic computations involving transducer automata.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Koblitz curvesFrobenius endomorphismScalar Multiplication$tau$-adic expansionsNon-Adjacent-FormsDigit SetsEfficient Implementation
Contact author(s)
clemens heuberger @ tugraz at
History
Short URL
https://ia.cr/2008/153

CC BY

BibTeX

@misc{cryptoeprint:2008/153,
author = {Clemens Heuberger},
title = {Redundant $\tau$-adic Expansions II: Non-Optimality and Chaotic Behaviour},
howpublished = {Cryptology ePrint Archive, Paper 2008/153},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/153}},
url = {https://eprint.iacr.org/2008/153}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.