Generating Elliptic Curves of Known Order

E. Savas, T. A. Schmidt, and C. K. Koc

Cryptographic Hardware and Embedded Systems - CHES 2001, C. K. Koc, D. Naccache, and C. Paar, editors, Third International Workshop, Paris, France, pages 142-158, Springer Verlag, LNCS Nr. 2162, May 14-16, 2001.

Abstract

In this paper, we give a methodology to generate suitable elliptic curves over GF(p). Our method is based on the Complex Multiplication (CM) technique. A previously proposed method which is also based on the CM technique assumes that the characteristic p of GF(p) is fixed. However, there are numerous primes within the range of cryptographic interest and flexibility in selecting a prime as the characteristic of the field allows simplification of the complex multiplication curve generation algorithm. Based on this observation, we modify the existing algorithm and provide performance results of our new algorithm. With this modified algorithm, we can utilize prime numbers in certain subsets of all prime numbers. Theoretical analysis and experimental figures show that there are sufficiently many primes in this set so that it is always possible to find such primes after several trials. We also provide experimental results on the plentitude of elliptic curves. The software implementation of the proposed method is faster, smaller, and also it is very easy to code.