Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time

(with Andrew Sutherland)

LMS J. Comput. Math. 17 (2014), Special Issue A, 257–273 (DOI).

(Proceedings of 11th Algorithmic Number Theory Symposium)

arXiv preprint (February 2014).


We present an efficient algorithm to compute the Hasse–Witt matrix of a hyperelliptic curve C/Q modulo all primes of good reduction up to a given bound N, based on the average polynomial-time algorithm recently introduced by Harvey. An implementation for hyperelliptic curves of genus 2 and 3 is more than an order of magnitude faster than alternative methods for N = 226.


In step 2 of the RemainderTree algorithm, the variable i should go down to zero, not 1. (Thanks to Maike Massierer for catching this.)

Back to the main page