Constructing elliptic curves in almost polynomial time

Details Constructing elliptic curves in almost polynomial time Constructing elliptic curves in almost polynomial time

2005-11-30

arxiv.org/abs/math/0511729v1

Mathematics

Number Theory

20 pages, 4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Constructing elliptic curves in almost polynomial time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructing elliptic curves in almost polynomial time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing elliptic curves in almost polynomial time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-430068