Elliptic curves over number fields with CM can be used to design non-isogenous elliptic cryptosystems over finite fields efficiently.
The existing algorithm to build such CM curves, so-called the CM field algorithm, is based on analytic expansion of modular
functions, costing computations of
O(2
5h/2
h
21/4) where
h is the class number of the endomorphism ring of the CM curve. Thus it is effective only in the small class number cases.
This paper presents polynomial time algorithms in h to build CM elliptic curves over number fields. In the first part, probabilistic probabilistic algorithms of CM tests are
presented to find elliptic curves with CM without restriction on class numbers. In the second part, we show how to construct
ring class fields from ray class fields. Finally, a deterministic algorithm for lifting the ring class equations from small
finite fields thus construct CM curves is presented. Its complexity is shown as O(h
7).