On the Efficient Generation of Prime-Order Elliptic Curves∗

Abstract. We consider the generation of prime-order elliptic curves (ECs) over a prime field Fp using the Complex Multiplication (CM) method. A crucial step of this method is to compute the roots of a special type of class field polynomials with the most commonly used being the Hilbert and Weber ones. These polynomials are uniquely determined by the CM discriminant D. In this paper, we consider a variant of the CM method for constructing elliptic curves (ECs) of prime order using Weber polynomials. In attempting to construct prime-order ECs using Weber polynomials, two difficulties arise (in addition to the necessary transformations of the roots of such polynomials to those of their Hilbert counterparts). The first one is that the requirement of prime order necessitates that D ≡ 3 (mod 8), which gives Weber polynomials with degree ∗ This work was partially supported by the IST Programme of EU under contracts no. IST-2001-33116 (FLAGS), and by the Action IRAKLITOS (Fellowships for Research in the University of Patras) with match