hypellfrob

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.

Source code

Latest version

Older versions

Example timings (updated Oct 2008)

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).

pgenus 2genus 3genus 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.)

A big example

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^3
where
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.)


Back to the main page