Fast Generation of Elliptic Curve Base Points Using Efficient Exponentiation over $GF(p^m)$)
Mun‐Kyu Lee · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2007
Since Koblitz and Miller suggested the use of elliptic curves in cryptography, there has been an extensive literature on elliptic curve cryptosystem (ECC). The use of ECC is based on the observation that the points on an elliptic curve form an additive group under point addition operation. To realize secure cryptosystems using these groups, it is very important to find an elliptic curve whose group order is divisible by a large prime, and also to find a base point whose order equals this prime. While there have been many dramatic improvements on finding an elliptic curve and computing its group order efficiently, there are not many results on finding an adequate base point for a given curve. In this paper, we propose an efficient method to find a random base point on an elliptic curve defined over . We first show that the critical operation in finding a base point is exponentiation. Then we present efficient algorithms to accelerate exponentiation in . Finally, we implement our algorithms and give experimental results on various practical elliptic curves, which show that the new algorithms make the process of searching for a base point 1.62-6.55 times faster, compared to the searching algorithm based on the binary exponentiation.