Reinier Bröker, Everett W. Howe, Kristin E. Lauter, and Peter Stevenhagen: Genus-2 curves and Jacobians with a given number of points, LMS Journal of Computation and Mathematics 18 (2015) 170–197.

Official version here. Preprint version: arXiv:1403.6911 [math.NT].

We study the problem of efficiently constructing a curve C of genus 2 over a finite field F for which either the curve C itself or its Jacobian has a prescribed number N of F-rational points.

In the case of the Jacobian, we show that any ‘CM-construction’ to produce the required genus-2 curves necessarily takes time exponential in the size of its input.

On the other hand, we provide an algorithm for producing a genus-2 curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-2 curve having exactly 102014 + 9703 (prime) points, and two genus-2 curves each having exactly 102013 points.

In an appendix we provide a clean and complete parametrization, over an arbitrary base field k of characteristic neither 2 nor 3, of the family of genus-2 curves over k that have k-rational degree-3 maps to elliptic curves, including formulas for the genus-2 curves, the associated elliptic curves, and the degree-3 maps.

Here are links to some Magma programs related to the paper: