Fast Scalar Multiplication Algorithm on Elliptic Curve over Optimal Extension Fields
Chung Byungchun, Soojin Lee, Seongmin Hong, Yoon Hyunsoo · Information Security and Cryptology · 2005
Speeding up scalar multiplication of an elliptic curve point has been a prime approach to efficient implementation of elliptic curve schemes such as EC-DSA and EC-ElGamal. Koblitz introduced a expansion method using the Frobenius map. Kobayashi et al. extended the scalar multiplication method to suit Optimal Extension Fields(OEF) by introducing the table reference method. In this paper we propose an efficient scalar multiplication algorithm on elliptic curve over OEF. The proposed scalar multiplication method uses an optimized batch technique after rearranging the computation sequence of expansion usually called Horner's rule. The simulation results show that the new method accelerates the scalar multiplication about over the Kobayashi et al. method and is about three times as fast as some conventional scalar multiplication methods.