Counting points on hyperelliptic curves in average polynomial time (Q2445320)

An hyperelliptic curve \(X\) of genus \(g\) and a rational Weierstrass point over a finite field \(\mathbb F_q\), \(q\) odd, can be written as \(y^2=Q(x)\) where \(Q\in\mathbb F_q\) is monic, square-free and of degree \(2g+1\). The zeta function of \(X\) has the form \[ Z_X(T)=\frac{P(T)}{(1-T)(1-qT)}, \] where \(P\in\mathbb Z[T]\) has degree \(2g\). An efficient algorithm for computing \(P(T)\), given \(q\), \(g\) and \(Q\), is useful for collecting data for the Birch-Swinnerton-Dyer conjecture and the Sato-Tate conjecture. Known algorithms for computing the zeta function have a time complexity that is exponential in either \(g\) or in \(\log p\). The author presents an algorithm that, for input \(N\geq 3\), \(g\geq 1\) and \(Q\in\mathbb Z[x]\) defining an hyperelliptic curve of genus \(g\), computes the sequence of zeta functions for \(\bar{X}_p\), over \(\mathbb F_p\), for all odd primes \(p < N\). The average time per prime is: \(g^{8+\epsilon}\log^3 N\log (\|Q\|N)\), which is polynomial in the size of the input (here \(\|Q\|\) denotes the maximum of the absolute values of the coefficients of \(Q\)). The starting point is \textit{K. S. Kedlaya}'s algorithm [J. Ramanujan Math. Soc. 16, No. 4, 323--338 (2001; Zbl 1066.14024)]. The portion of this algorithm whose complexity is exponential in \(\log p\) involves computing certain ``reduction matrices''. The main improvement comes from replacing these by matrices that do not depend on \(p\). Then the author adopts the accumulating remainder tree algorithm of Costa, Gerbicz and Harvey, replacing its linear polynomials with his new matrices.