Constructing elliptic curves in almost polynomial time
From MaRDI portal
Publication:6476381
arXivmath/0511729MaRDI QIDQ6476381FDOQ6476381
Authors: Reinier Bröker, Peter Stevenhagen 
Publication date: 30 November 2005
Abstract: 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^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+epsilon}) can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order N=10^2004 and N=nextprime(10^{2004})=10^{2004}+4863.
This page was built for publication: Constructing elliptic curves in almost polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6476381)
