A Point Counting Algorithm for Cyclic Covers of the Projective Line

We present a Kedlaya-style point counting algorithm for cyclic covers $y^r = f(x)$overafinitefield$$\mathbb{F}$_{p^n}$with$p$notdividing$r$,and$r$and$\deg{f}$ not necessarily coprime. This algorithm generalizes the Gaudry-G"urel 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 $\mathcal{C}$, refined bounds on the $p$-adic precision, and an alternative pseudo-basis for the Monsky-Washnitzer cohomology which leads to an integral matrix when $p \geq 2r$. Each of these improvements can also be applied to the original Gaudry-G"urel algorithm. We include some experimental results, applying our algorithm to compute Weil polynomials of some large genus cyclic covers.