Abstract: We consider the generation of primeorder 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 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 primeorder 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
primeorder 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 primeorder ECs. Finally, we compare
experimentally the efficiency of using this new class against the use of
the aforementioned Weber polynomials.
Keywords: Elliptic Curve Cryptosystems,
Abstract: We consider a variant of the Complex Multiplication (CM)
method for constructing elliptic curves (ECs) of primeorder with additional
security properties. Our variant uses Weber polynomials whose
discriminant D is congruent to 3 (mod 8), and is based on a new transformation
for converting roots of Weber polynomials to their Hilbert
counterparts. We also present a new theoretical estimate of the bit precision
required for the construction of the Weber polynomials for these
values of D. We conduct a comparative experimental study investigating
the time and bit precision of using Weber polynomials against the (typical)
use of Hilbert polynomials. We further investigate the time efficiency
of the new CM variant under four different implementations of a crucial
step of the variant and demonstrate the superiority of two of them.
Abstract: We consider the generation of prime-order elliptic curves (ECs) over a prime field $\mathbb{F}_{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 primeorder 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 primeorder 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 $\mathbb{F}_{p}$ .
In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of primeorder focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field $\mathbb{F}_{p^{3}}$ and present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^{3}}$ to roots of their corresponding Hilbert polynomials in $\mathbb{F}_{p}$ . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_{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.
