Total views : 272

Maximum and Minimum Norms for τ-NAF Expansion on Koblitz Curve


  • Institute for Mathematical Research, Universiti Putra Malaysia, 43400 Serdang, Selangor, Malaysia
  • Mathematical Department, Faculty of Science, Universiti Putra Malaysia, 43400 Serdang, Selangor, Malaysia


Background/Objectives: The scalar multiplication in Elliptic Curve Cryptosystem (ECC) is the dominant operation of computing integer multiple for an integer n and a point P on elliptic curve. In 1997, Solinas4 introduced the τ-adic non-adjacent form (τ-NAF) expansion of an element n of ring Z(τ) on Koblitz Curve. However in 2000, Solinas estimated the length of τ-NAF expansion by using maximum and minimum norms that obtained by direct evaluation method. In 2014, Yunos et al.9 introduced the formula of norm for every τ-NAF to improve this method. However, a lot of combination of norm should be considered when length of expansion is more than 15. So, the objective of this paper is to built the formulas to calculate the number of maximum and minimum norms for τ-NAF occurring among of all elements in Z(τ). Application/Improvement: With these formulas, we can estimate the length of τ-NAF expansion more accurately.


τ-adic Non-Adjacent Form (τ-NAF), Koblitz Curve, Maximum and Minimum Norms.

Full Text:

 |  (PDF views: 201)


  • Miller V. Use of elliptic curve in cryptography. Advance in Cryptology, Proc.Crypto’85, Proceedings Springer; 1986. p. 417–26.
  • Koblitz N. Elliptic curve cryptosystem. Mathematics Computation. 1987; 8(177):203–9.
  • Koblitz N. CM-curves with good cryptographic properties. Advance in Cryptology, Proc. Crypto’91, Springer; 1992. p. 279–87.
  • Solinas JA. An improved algorithm for arithmetic on a family of elliptic curves. Advance in Cryptology, Proc. CRYPTO’97, Springer; 1997. p. 357–71.
  • Solinas JA. Efficient arithmetic on Koblitz curves. Design, Codes, and Cryptography. 2000; 19:195–249.
  • Joye M, Tymen C. Protection against differential analysis for elliptic curve cryptography: an algebraic approach. Cryptography Hardware and Embedded Systems-CHES01, Springer; 2001. p. 377–90.
  • Hedabou M. A Frobenious map approach for an efficient and secure multiplication on Koblitz curves. International Journal of Network Security. 2006; 3(3):233–7.
  • Avanzi RM, Heuberger C, Prodinger H. Minimality of the Hamming weight of the ô-NAF for Koblitz curves and improved combination with point halving. Select-ed Areas in Cryptography, Springer Science & Business Media. 2006.
  • Yunos F, Atan MKA, Ariffin KMR, Said MMR. Pertanika Journal of Science & Technology. 2014; 22.
  • NIST [Internet]. [Cited 2013 Jul]. Available from: http:/nvlpubs. 186-4.pdf.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.