Efficient CM-constructions of elliptic curves over finite fields

Abstract:

We present an algorithm that, on input of an integer $N\ge 1$ together with its prime factorization, constructs a finite field $\mathbf {F}$ and an elliptic curve $E$ over $\mathbf {F}$ for which $E({\mathbf {F} })$ has order $N$. Although it is unproved that this can be done for all $N$, a heuristic analysis shows that the algorithm has an expected run time that is polynomial in $2^{\omega (N)}\log N$, where $\omega (N)$ is the number of distinct prime factors of $N$. In the cryptographically relevant case where $N$ is prime, an expected run time $O((\log N)^{4+\varepsilon })$ can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order $N=10^{2004}$ and $N=\text {nextprime}(10^{2004})=10^{2004}+4863$.