A Point Counting Algorithm for Cyclic Covers of the Projective Line

March 14, 2016

Cecile Gonçalves (LACL)

We present a Kedlaya-style point counting algorithm for cyclic covers of the projective line over a finite field. This algorithm generalizes the Gaudry-Gürel algorithm for superelliptic curves to a more general class of curves, and has essentially the same complexity. Our practical improvements include a simplified algorithm exploiting the automorphism of the curve, refined bounds on the p-adic precision, and an alternative pseudo-basis for the Monsky-Washnitzer cohomology which leads to an integral matrix in some cases we will precise. Each of these improvements can also be applied to the original Gaudry-Gürel algorithm. Our algorithm allowed us to compute Weil polynomials of some large genus cyclic covers.