@article{MR2643687,
  abstract = {We consider the generation of prime-order elliptic curves (ECs) over a prime field 𝔽p 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?3mod8), which gives Weber polynomials with degree three times larger than the degree of their corresponding Hilbert polynomials (a fact that could affect efficiency). The second difficulty is that these Weber polynomials do not have roots in 𝔽p . In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field 𝔽p3 and present a set of transformations for mapping roots of Weber polynomials in 𝔽p3 to roots of their corresponding Hilbert polynomials in 𝔽p . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in 𝔽p ), can be used in the CM method to generate prime-order ECs. We conduct an extensive experimental study comparing the efficiency of using this alternative class against the use of the aforementioned Weber polynomials. Finally, we investigate the time efficiency of the CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them. },
  file = {cryptology.pdf},
  mrclass = {14G50 (11G15 11R37 11T71 14G15 14K22 94A60)},
  mrnumber = {2643687 (2012f:14051)},
  issn = {0933-2790},
  number = {3},
  year = {2010},
  url = {http://dx.doi.org/10.1007/s00145-009-9037-2},
  author = {Konstantinou, Elisavet and Kontogeorgis, Aristides and Stamatiou, Yannis C. and Zaroliagis, Christos},
  mrreviewer = {Juan Tena},
  pages = {477--503},
  volume = {23},
  fjournal = {Journal of Cryptology. The Journal of the International Association for Cryptologic Research},
  doi = {10.1007/s00145-009-9037-2},
  coden = {JOCREQ},
  journal = {J. Cryptology},
  title = {On the efficient generation of prime-order elliptic curves}
}