Constructing elliptic curves and curves of genus 2 over finite fields (Q2829798)

The paper gives a survey of methods to construct elliptic curves and genus 2 curves defined over a prime finite field \(\mathbb{F}_l\)\, with the cardinal of the elliptic curve and the Jacobian of the genus 2 curve given (in cryptographic applications these cardinals must be primes or quasiprimes). The author pays special attention to algorithms that use the Chinese remainder theorem (CRT).NEWLINENEWLINESection 2 discusses the elliptic curve case. To find an ordinary elliptic curve over \(\mathbb{F}_l\)\, with cardinal \(N\)\, (\(N\)\, in the Hasse interval), according to the complex multiplication method, one has to build the Hilbert class polynomial \(H_D(X)\)\, of the quadratic field \(K=\mathbb Q(\sqrt{D});\, D=t^2-4l,\, t=l+1-N)\)\, and then to take a root of \(H_D(X)\)\, modulo \(l\), see [\textit{A. O. L. Atkin} and \textit{F. Morain}, Math. Comput. 61, No. 203, 29--68 (1993; Zbl 0792.11056)]. The paper describes an algorithm to compute \(H_D(X)\)\, due to \textit{A. Agashe} et al. [in: High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Selected papers from the international conference on number theory, Banff, AB, Canada, May 24--30, 2003. Providence, RI: American Mathematical Society (AMS). 1--17 (2004; Zbl 1102.11031)]. The algorithm computes \(H_D(X)\)\, modulo sufficiently many small primes and then uses the CRT to find \(H_D(X)\). An improvement of the method due to \textit{J. Belding} et al. [Lect. Notes Comput. Sci. 5011, 282--295 (2008; Zbl 1205.11139)] has expected running time \(\tilde{O}(|D|)\).NEWLINENEWLINESection 3 deals with the case of a genus two curve \(\mathcal{C}\). In this case the problem is, given positive integers \(N_1, N_2\),\, to find \(\mathcal{C}\)\, such that \(\sharp(\mathcal{C}(\mathbb{F}_l))=N_1\)\, and \(\sharp(\mathcal{C}(\mathbb{F}_{l^2}))=N_2\)\, (then \(\sharp(J(\mathcal{C})(\mathbb{F}_l))=(N_1^2+N_2)/2 -l\)). Now we have a CM quartic field \(K\)\, and we have to construct the three Igusa class polynomials of \(K\),\, \(H_j,\, j=1,2,3\). To compute these polynomials \textit{K. Eisenträger} and \textit{K. Lauter} [in: Arithmetics, geometry and coding theory (AGCT 2005). Papers of the conference held at CIRM, Marseille, France, 2005. Paris: Société Mathématique de France. 161--176 (2009; Zbl 1270.11060)] propose an algorithm which computes first the polynomials modulo some small primes and then uses the CRT.NEWLINENEWLINEFor the entire collection see [Zbl 1345.11003].