Pre-computation in Width-w τ-adic NAF Implementations on Koblitz Curves

Abstract

This paper examines scalar multiplication on Koblitz curves employing the Frobenius endomorphism. We examine simple binary scalar multiplication, binary Non Adjacent Formats or NAF's, followed by τ-NAF methods. We pay particular attention to width-τ-NAF where we focus on pre-computation. We present alternative pre-computation arrangements for αu for width sizes of 5 and 6 which are better than any previously published results since they: involve a single power of τ are based on least norms; and have a maximum of 2w - 2 - 1 elliptic curve operations. We then study widths of 7 and 8 producing efficient arrangements. Arrangements for width sizes of 7 and 8 have never before appeared in the literature. Furthermore, we introduce a simplified rounding technique for reduction modulo (τm - 1)/(τ - 1) relaxing the requirement of least norms. Lastly, we discuss an O(n) technique for finding arbitrary powers of &tau in software.