Official version here.

Preprint version: arXiv:1506.04478 [math.NT].

The *defect* of a curve over a finite field is the difference between the
number of rational points on the curve and the Weil–Serre bound for the curve.
We present a construction for producing genus-4 double covers of genus-2
curves over finite fields such that the defect of the double cover is not much
more than the defect of the genus-2 curve. We give an algorithm that uses
this construction to produce genus-4 curves with small defect. Heuristically,
for large primes *q*, the algorithm is expected to produce a genus-4 curve
over **F**_{q} with defect at most 4 in time *q*^{3/4},
up to logarithmic factors.

As part of the analysis of the algorithm, we present a reinterpretation of results of Hayashida on the number of genus-2 curves whose Jacobians are isomorphic to the square of a given elliptic curve with complex multiplication by a maximal order. We show that a category of principal polarizations on the square of such an elliptic curve is equivalent to a category of right ideals in a certain quaternion algebra.

Soon, a Magma implementation of the algorithms in the paper will be made available here.