hypellfrob is a C++ program/library for computing the zeta function of a hyperelliptic curve over GF(p), based on the method described in the paper Kedlaya's algorithm in larger characteristic. More precisely, it computes the matrix of Frobenius on the Monsky-Washnitzer cohomology of the curve; the zeta function can be recovered via the characteristic polynomial of the matrix.
It depends on NTL and zn_poly.
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 |