Currently available as a preprint and an official version, which you should be able to access without paying anything if you use that link. On the other hand, that versions is not downloadable, so if you want to have a local copy, then use this paywalled version.
We present an algorithm that, for every fixed genus g, will enumerate all hyperelliptic curves of genus g over a finite field k of odd characteristic in quasilinear time; that is, the time required for the algorithm is Õ(q2g–1), where q = #k. Such an algorithm already exists in the case g = 2, thanks to the work of Mestre and Cardona and Quer on reconstructing genus-2 curves from their Igusa invariants, and in the case g = 3, thanks to work of Lercier and Ritzenthaler. Experimentally, it appears that our new algorithm is about two orders of magnitude faster in practice than ones based on their work.
We have implemented our algorithm for hyperelliptic curves of genus 2 and genus 3. Magma files with the implementations can be found here: