Everett W. Howe: Quickly constructing curves of genus 4 with many points, pp. 149–173 in: Frobenius Distributions: Sato–Tate and Lang–Trotter conjectures (D. Kohel and I. Shparlinski, eds.), Contemporary Mathematics 663, American Mathematical Society, Providence, RI, 2016.

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 Fq with defect at most 4 in time q3/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.