Enumerating places of ${\mathbf{P}}^1$ up to automorphisms of ${\mathbf{P}}^1$ in quasilinear time

Abstract

We present an algorithm that, for every fixed degree $n\ge 3$, will enumerate all degree-$n$ places of the projective line over a finite field $k$ up to the natural action of ${\mathrm{PGL}}_2(k)$ using $O(\log q)$ space and $\tilde{O}(q^{n-3})$ time, where $q=\#k$. Since there are $\Theta (q^{n-3})$orbits of ${\mathrm{PGL}}_2(k)$ acting on the set of degree-$n$ places, the algorithm is quasilinear in the size of its output. The algorithm is probabilistic unless we assume the extended Riemann hypothesis. We also present an algorithm for enumerating orbit representatives for the action of ${\mathrm{PGL}}_2(k)$ on the degree-$n$ effective divisors of ${\mathbf{P}}^1$ over finite fields $k$. The two algorithms depend on one another; our method of enumerating orbits of places of odd degree $n$ depends on enumerating orbits of effective divisors of degree $(n+1)/2$. As an application of the second algorithm, for $g=2$, $3$, and $4$ we implement an algorithm in Magma that computes all hyperelliptic curves of genus $g$ over finite fields $k$ using $O(q^{g-1})$ space and $\tilde{O}(q^{2g-1})$ time, where $q=\#k$. Our implementation runs $60$--$80$ times faster than existing algorithms for computing genus-$2$ hyperelliptic curves, and about $280$ times faster than existing algorithms for computing genus-$3$ hyperelliptic curves. We know of no other implementations of algorithms to compute genus-$4$ hyperelliptic curves.

24 pages