A point counting algorithm for cyclic covers of the projective line (Q2811791)

The present paper provides a point counting algorithm for some plane curves defined over a finite field, in fact the class of curves with affine equation \(C:y^r=f(x)\) (including therefore elliptic and hyperelliptic curves) over \(\mathbb{F}_q,\, q=p^n,\, p\nmid r\).NEWLINENEWLINEThe proposed algorithm generalizes the algorithm of \textit{P. Gaudry} and \textit{N. Gürel} [Lect. Notes Comput. Sci. 2248, 480--494 (2001; Zbl 1064.11080)] for superelliptic curves (curves with \(\mathrm{gcd}(r, d=d^{o}f)=1)\). The author points out that ``our algorithm has essentially the same complexity as the Gaudry-Gürel algorithm'' (in the best case \(\tilde{O}(pn^3d^4r^3)\) elementary operations), but he enumerates three main simplifications and improvements.NEWLINENEWLINESection 2 recalls the concept of cyclic cover of the projective line and Section 3 studies the action of the Frobenius automorphism on the first Monsky-Washnitzer cohomology group \(H^1_{MW}(C,\mathbb{Q}_q)\). Then Section 4 presents the point counting algorithm for \(C\) (Algorithm 1). Theorem 4.1 computes the Weil polynomial of \(C\)\, and Theorem 4.3 (whose proof is postponed to Section 6) gives the precision \(p\)-adic bounds needed to recover the Weil polynomial over \(\mathbb{Z}_q\). Then the paper details the steps of Algorithm 1 and Section 8 shows four numerical examples using Magma 2.18.NEWLINENEWLINEFor the entire collection see [Zbl 1317.11007].