On the Optimal Pre-Computation of Window NAF for Koblitz Curves
William R. Trost, Guangwu Xu · IEEE Transactions on Computers · 2015
Koblitz curves have been an important subject of consideration for both theoretical andpractical interests. The window$\tau$-adic algorithm of Solinas (window$\tau$NAF) is the most powerful method for computing point multiplication for Koblitz curves.Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window$\tau$NAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires$2^{w-2}-1$point additions and two evaluations of the Frobenius map$\tau$, where$w$is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width$w$from$4$to$15$(more than practical needs).These pre-computations can be easily incorporated into implementations of window$\tau$NAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper includes a discussion of coefficient sets for window$\tau$NAF and the divisibility by powers of$\tau$through different approaches. Some issues of implementation are also discussed.