Constructing elliptic curves in almost polynomial time

Original · EN

We present an algorithm that, on input of a positive integer N together with its prime factorization, constructs a finite field F and an elliptic curve E over F for which E(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ᵒmega(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+epsilon) can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order N=10²004 and N=nextprime(10²⁰⁰⁴)=10²⁰⁰⁴+4863.