A Novel Window \(\tau \) NAF on Koblitz Curves

The window \(\tau \) -adic non-adjacent form (window \(\tau \) NAF) was initially proposed by Solinas in 2000 as a method to calculate scalar multiplication on the Koblitz curves. To ensure the correctness of the window \(\tau \) NAF, Blake, Murty, and Xu demonstrated that the pre-computation scheme of this method must be convergent. To date, the standard representation system for scalar multiplication on the Koblitz curve \(E_a/ \mathbb {F}_{2^m}\) using the Frobenius map \(\tau \) remains the window \(\tau \) NAF. In this paper, we present a novel algorithm that extends the window \(\tau \) NAF approach and improves its pre-computation scheme. Our algorithm integrates several window \(\tau \) NAFs, where the initial few are non-convergent and the final one is the standard window \(\tau \) NAF. Compared with the previous state-of-the-art method, our approach achieves a \(5\%\) reduction in the time for implementing scalar multiplication when using the \(\mu _4\) -Koblitz curves and LD coordinates. This work offers significant advancements in optimizing scalar multiplication on Koblitz curves.