A point counting algorithm for cyclic covers of the projective line

DOI10.1090/CONM/637/12754MaRDI QIDQ2811791zbMATH OpenOpenAlexFDO

Authors Cécile Gonçalves

Publication date 10 June 2016

Published in Algorithmic Arithmetic, Geometry, and Coding Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2095

zbMATH Keywords

\(p\)-adic precisionalgebraic geometrycyclic covernumber theorypoint counting

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Rational points (14G05) Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture) (14G10) Finite ground fields in algebraic geometry (14G15) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 $degf$ 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 $mathcalC$, refined bounds on the $p$-adic precision, and an alternative pseudo-basis for the Monsky-Washnitzer cohomology which leads to an integral matrix when $pgeq2r$. 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.

Review text

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].

Recommendations

• Counting points on superelliptic curves in average polynomial time
• scientific article; zbMATH DE number 2081082
• A point counting algorithm using cohomology with compact support
• scientific article; zbMATH DE number 1775200
• Quasi-quadratic elliptic curve point counting using rigid cohomology
• Counting (quickly) the number of solutions of equations in finite fields
• Computing zeta functions of algebraic curves using Harvey's trace formula
• Computing period matrices and the Abel-Jacobi map of superelliptic curves
• A p-Adic Quasi-Quadratic Time Point Counting Algorithm
• The canonical lift of an ordinary elliptic curve over a finite field and its point counting

Cited in

(5)

• Counting points on superelliptic curves in average polynomial time
• Computing zeta functions of cyclic covers in large characteristic
• Explicit Coleman integration in larger characteristic
• Square root time Coleman integration on superelliptic curves
• Elliptic Gauss sums and applications to point counting

Describes a project that uses

Uses Software

• Magma

This page was built for publication: A point counting algorithm for cyclic covers of the projective line

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811791)