Speeding Up the Double-Base Recoding Algorithm of Scalar Multiplication∗
Haihua Gu, Dawu Gu · Cryptologia · 2009
Scalar multiplication nP is the core operation of elliptic curve public-key cryptosystems. Double bases representation of n is proposed to speed up scalar multiplication. Avanzi et al. presented a recoding algorithm for Koblitz curves which works in all cases with optimal constants [1 Avanzi , R. , V. Dimitrov , C. Doche , and F. Sica . 2006 . “Extending Scalar Multiplication Using Double Bases, In Proc. ASIACRYPT '06,” Lecture Notes in Computer Science , 4284 : 130 – 144 .[Crossref] , [Google Scholar]]. However, their algorithm may be expensive to implement because it requires many divisions in ℤ[τ]. In this paper, we show that divisions in ℤ[τ] can be replaced by divisions in ℤ. Our improved version of the algorithm runs in about 33% of the time of the Avanzi et al. algorithm on the Koblitz curve K-163, with larger improvements as the size of the curve increases.