Enumerating hyperelliptic curves over finite fields in quasilinear time

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 (O) over tilde (q(2g-1)), where q=#k. Such an algorithm already exists in the case g=2, thanks to work of Mestre and Cardona and Quer, 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.