These are timings for random hyperelliptic curves over GF(p), performed on sage.math, a 1.8GHz AMD Opteron (thanks to William Stein), using hypellfrob version 2.0 and zn_poly version 0.4.
For genus 2, we computed the charpoly mod p, which determines essentially all the information. For genus 3, we also compute the charpoly mod p, which leaves half a digit to be recovered by e.g. baby-step/giant-step. For genus 4, we computed the charpoly mod p^2, which determines essentially everything.
|p||genus 2||genus 3||genus 4|
|2^16 + 1||0.008s||0.020s||0.16s|
|2^20 + 7||0.044s||0.092s||0.92s|
|2^24 + 43||0.324s||0.648s||20.3s|
|2^28 + 3||2.95s||5.9s||111s|
|2^32 + 15||21.6s||43.3s||1313s|