Efficient CM-constructions of elliptic curves over finite fields
Reinier Bröker, Peter Stevenhagen · Mathematics of Computation · 2007
We present an algorithm that, on input of an integer N ≥ 1 N\ge 1 together with its prime factorization, constructs a finite field F \mathbf {F} and an elliptic curve E E over F \mathbf {F} for which E ( F ) E({\mathbf {F} }) has order N N . Although it is unproved that this can be done for all N N , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in 2 ω ( N ) log N 2^{\omega (N)}\log N , where ω ( N ) \omega (N) is the number of distinct prime factors of N N . In the cryptographically relevant case where N N is prime, an expected run time O ( ( log N ) 4 + ε ) O((\log N)^{4+\varepsilon }) can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order