A Note on the TNAF Algorithm on Koblitz Curves

To implement fast encryption of data Koblitz first introduced a family of elliptic curves defined over F 2 and gave a kind of fast algorithm for performing elliptic scalar multiplication utilizing the Frobenius map. Solinas rigorously defined TNAF in Z, which exists uniquely for a given integer, and improved and generalized Koblitz's ideas. Following the relevant results of standard binary expansion the anthors further prove that for any element α of Z, its τ adic NAF has the fewest Hamming weight of any signed τ adic expansions of α. In such a sense the TNAF algorithm on Koblitz curves is optimal. A specific algorithm for convert signed τ adic expansions to TNAFs is simultaneously presented in the process of proof.