While speeding up modular exponentiation has been a prime approach to speeding up the RSA scheme, scalar multiplication of an elliptic curve point can speed up elliptic curve schemes such as EC-DSA and EC-ElGamal. Bailey and Paar newly proposed an elliptic curve scheme on Optimal Extension Fields(OEFs) at Crypt'98 and Kobayashi et al. extended the base-Φ scalar multiplication method to suit OEFs by introducing the table reference method at Eurocrypt'99.
In this thesis, we propose a new elliptic curve scalar multiplication on OEFs by using the Frobenius map and the batch technique. The proposed base-Φ scalar multiplication method uses an optimized batch technique by rearranging the computation sequence usually called "Horner's rule".
Finally, we analyze and evaluate the performance of the proposed base-Φ scalar multiplication method and compare it with previous methods. The simulation results show that our method accelerates the scalar multiplication about 20% over the Kobayashi's method and is about three times as fast as some conventional scalar multiplication methods.
