An efficient method to generate elliptic curves

Abstract

In this paper, an efficient method to generate elliptic curves for public key cryptosystems based on discrete logarithm problem is presented. Usually, to resist possible attacks, such as MOV reduction, public key cryptosystems based on elliptic curve E over field GF（q） must satify the following condition: the order m of the curve has a large prime factor of the form 2p+1 where p is a prime and q21 mod m. This condition can be relaxed to include primes of the form 2ip+1 （i is a small integer） without compromising security. Hence, the number of elliptic curves suitable for use by public key cryptosystems is increased greatly. We design a method to implement such a scheme, showing that, it is much faster to generate a suitable elliptic curve with this new scheme than with the original scheme.

Keywords

• public key cryptosystem
• elliptic curve generation