Date of Award


Degree Type


Degree Name

Master of Science


Computer Science

First Advisor

Guangwu Xu

Committee Members

Christine Cheng, Adrian Dumitrescu


Cryptography, Elliptic Curve, Koblitz, Tau NAF, TNAF, Window Tau NAF


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.