On the Efficient Generation of PrimeOrder Ellipti

Authors: Elisavet Konstantinou Aristides Kontogeorgis Yannis C Stamatiou Christos Zaroliagis

Publish Date: 2009/03/31

Volume: 23, Issue: 3, Pages: 477-503

PDF Link

Abstract

We consider the generation of primeorder elliptic curves ECs over a prime field mathbbF 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 primeorder 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 mathbbF 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 mathbbF p3 and present a set of transformations for mapping roots of Weber polynomials in mathbbF p3 to roots of their corresponding Hilbert polynomials in mathbbF p We also show how an alternative class of polynomials with degree equal to their corresponding Hilbert counterparts and hence having roots in mathbbF p can be used in the CM method to generate primeorder 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 themThis work was partially supported by the IST Programme of EU under contracts no IST200133116 FLAGS and by the Action IRAKLITOS Fellowships for Research in the University of Patras with matching funds from ESF European Social Fund and the Greek Ministry of Education

Keywords: