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 10^{2014} + 9703 (prime) points,
and two genus-2 curves each having exactly 10^{2013} 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:

- The file Genus2.magma contains implementations of all of the algorithms in the paper.
- The file Verification.magma contains code that verifies that the examples given in Section 7 of the paper are correct.