Non-Minimality of the Width-$w$ Non-adjacent Form in Conjunction with Trace One $\tau$-adic Digit Expansions and Koblitz Curves in Characteristic Two

Abstract

This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace $\pm 1$ as base and a minimal norm representatives digit set. For $w\ge 2$ it is shown that the width-$w$ non-adjacent form is not an optimal expansion, meaning that it does not minimize the (Hamming-)weight among all possible expansions with the same digit set. One main part of the proof uses tools from Diophantine analysis, namely the theory of linear forms in logarithms and the Baker--Davenport reduction method.