Efficient algorithms for Koblitz curves over fields of characteristic three

The nonadjacent form method of Koblitz [Advances in Cryptology (CRYPTO'98), in: Lecture Notes in Comput. Sci., vol. 1462, 1998, pp. 327-337] is an efficient algorithm for point multiplication on a family of supersingular curves over a finite field of characteristic 3. In this paper, a further discussion of the method is given. A window nonadjacent form method is proposed and its validity is proved. Efficient reduction and pre-computations are given. Analysis shows that more than 30% of saving can be achieved.