A Point Counting Algorithm for Cyclic Covers of the Projective Line
This work addresses a computational problem in algebraic geometry and cryptography for researchers, but it is incremental as it builds on existing algorithms with specific enhancements.
The paper tackles the problem of point counting for cyclic covers of the projective line over finite fields, presenting a Kedlaya-style algorithm that generalizes prior work to a broader class of curves with similar complexity, and includes practical improvements such as simplified computations and refined precision bounds, achieving experimental results for large genus cases.
We present a Kedlaya-style point counting algorithm for cyclic covers $y^r = f(x)$ over a finite field $\mathbb{F}_{p^n}$ with $p$ not dividing $r$, and $r$ and $°{f}$ not necessarily coprime. 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 $\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ürel algorithm. We include some experimental results, applying our algorithm to compute Weil polynomials of some large genus cyclic covers.