Redundant \(\tau \)-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication (Q629938)

Koblitz curves are elliptic curves over the finite field \({\mathbb F}_{2^n}\) defined by the equation \[ y^2+xy=x^3+ax^2+1, \quad a\in\{0,1\}, \] and with Frobenius endomorphism \(\tau\). The authors investigate properties of \(\tau \)-adic expansions of scalars. Solinas introduced the width-\(w\) \(\tau \)-adic non-adjacent form for use with Koblitz curves. This is an expansion of integers \({z = \sum_{i=0}^\ell z_i \tau^i}\), where \(\tau \) is a quadratic integer depending on the curve, such that \(z_{i } \neq 0\) implies \(z_{w+i-1} = \cdots = z_{i+1} = 0\). It uses a redundant digit set. The authors show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. Apart from this digit set of minimal norm representatives, other digit sets can be chosen such that all integers can be represented by a width-\(w\) non-adjacent form using those digits. They describe an algorithm recognizing admissible digit sets. Results by Solinas and by Blake, Murty, and Xu are generalized. In particular, they introduce two new useful families of digit sets. The first set is syntactically defined. As a consequence of its adoption they can also present improved and streamlined algorithms to perform the precomputations in \(\tau \)-adic scalar multiplication methods. The latter use an improvement of the computation of sums and differences of points on elliptic curves with mixed affine and López-Dahab coordinates. The second set is suitable for low-memory applications, generalizing an approach started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication algorithm that dispenses with the initial precomputation stage and its associated memory space. A suitable choice of the parameters of the method leads to a scalar multiplication algorithm on Koblitz curves that achieves sublinear complexity in the number of expensive curve operations.