| 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 tau-NAF methods. We pay particular attention to width-w tau-NAF where we focus on pre-computation. We present alternative pre-computation arrangements for alpha u for width sizes of 5 and 6 which are better than any previously published results since they: involve a single power of tau 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 (taum -- 1)/(tau -- 1) relaxing the requirement of least norms. Lastly, we discuss an O(n) technique for finding arbitrary powers of tau in software. |
