research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleGenerating Prime Order Elliptic Curves: Difficulties and Efficiency Considerations
Bibtex cite IDRACTI-RU1-2005-85
Booktitle Information Security and Cryptology
Series Lecture Notes in Computer Science
Year published 2005
Volume 3506
Pages 261-278
Organization ICISC 2004
Note Also in ICISC 2004
Keywords Elliptic Curve Cryptosystems,Generation of Prime Order Elliptic Curves,Complex Multiplication,Class Field Polynomials.
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, uniquely determined by the CM discriminant D. 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 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 Fp. In this paper we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order supported by a thorough experimental study. In particular, we show that such Weber polynomials have roots in F p3 and present a set of transformations for mapping roots of Weber polynomials in F p3 to roots of their corresponding Hilbert polynomials in Fp. We also show how a new class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in Fp), can be used in the CM method to generate prime order ECs. Finally, we compare experimentally the efficiency of using this new class against the use of the aforementioned Weber polynomials. Keywords: Elliptic Curve Cryptosystems,
Konstantinou, Elisavet
Kontogeorgis, A.
Stamatiou, Yannis
Zaroliagis, Christos
icisc2004-gen-prime-ec.pdf (main file)
Publication ID398