Constructing elliptic curves in almost polynomial time

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
20 pages, 4 figures

Keywords

Number Theory, Algebraic Geometry, 14H52; 11G20

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/105145

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0511729
 http://arxiv.org/abs/math/0511729

Collections

arXiv