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 a 2.6GHz AMD Opteron (thanks to the mathematics department at Harvard University), using hypellfrob 2.1.1, zn_poly 0.9, GMP 4.2.3 (plus assembly patches of Pierrick Gaudry), NTL 5.4.2.
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.
For genus 4, the jump in time at 2^24 is due to the implementation switching from zn_poly to NTL in the "vertical reduction" phase (which must be done modulo p^3 which is bigger than 64 bits).
p | genus 2 | genus 3 | genus 4 |
---|---|---|---|
2^16 - 15 | 0.006s | 0.013s | 0.097s |
2^20 - 3 | 0.025s | 0.050s | 0.470s |
2^24 - 3 | 0.168s | 0.332s | 12.1s |
2^28 - 57 | 1.04s | 2.11s | 55.3s |
2^32 - 5 | 6.54s | 13.1s | 809s |
2^36 - 5 | 34.1s | 68.0s |
(Older timings available here.)
Let p = 2^55 - 55 = 36028797018963913. Consider the genus 3 curve y^2 = f(x), where
f(x) = 12345678901234567 + 13579246801357924x + 23571113171923293x^2 + 31415926535897932x^3 + 27182818284590452x^4 + 5772156649015328x^5 + 6931471805599453x^6 + x^7,whose coefficients are well-known pseudo-random sequences of digits. We computed its zeta function modulo p using hypellfrob, and used Magma (2.14-15) to deduce the rest of the zeta function (the latter computation took a few seconds; the search space is only p^(1/2).) The main computation took 29.6 hours and had peak memory usage of 90 GB, on the same machine as described above. The numerator of the zeta function turns out to be
P(T) = T^6 + a1*T^5 + a2*T^4 + a3*T^3 + p*a2*T^2 + p^2*a1*T + p^3where
a1 = 167973286,
a2 = -22643031358365737,
a3 = -8125900295882638090771052.The number of points on the Jacobian is
N = P(1) = 46768052612630469688363681100781011334580612382848,which miraculously factors as
2^7 * 365375411036175544440341258599851651051411034241,where the latter is a prime factor close to 2^158. (We got pretty lucky this time.)