Efficient CM-constructions of elliptic curves over finite fields期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Efficient CM-constructions of elliptic curves over finite fields

Authors:	Reinier Brö ker Peter Stevenhagen.

Affiliation:	Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands. ; Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands.

Abstract:	We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in $2^{omega (N)}log N$ , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time $O((log N)^{4+varepsilon })$ can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order $N=10^{2004}$ and nextprime $(10^{2004})=10^{2004}+4863$ .

Keywords:

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载全文