Paper 2008/153

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

Clemens Heuberger


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)
Publication info
Published elsewhere. Unknown where it was published
Koblitz curvesFrobenius endomorphismScalar Multiplication$tau$-adic expansionsNon-Adjacent-FormsDigit SetsEfficient Implementation
Contact author(s)
clemens heuberger @ tugraz at
2008-04-08: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.