Constructing elliptic curves in almost polynomial time
| dc.creator | Broker, Reinier | |
| dc.creator | Stevenhagen, Peter | |
| dc.date | 2005-11-30 | |
| dc.date.accessioned | 2026-07-07T06:51:55Z | |
| dc.date.available | 2026-07-07T06:51:55Z | |
| dc.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. | |
| dc.description | 20 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/math/0511729 | |
| dc.identifier | http://arxiv.org/abs/math/0511729 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105145 | |
| dc.subject | Number Theory | |
| dc.subject | Algebraic Geometry | |
| dc.subject | 14H52; 11G20 | |
| dc.title | Constructing elliptic curves in almost polynomial time | |
| dc.type | text |