A point counting algorithm for cyclic covers of the projective line

DOI10.1090/CONM/637/12754zbMATH Open1343.14016arXiv1408.2095OpenAlexW4301353030MaRDI QIDQ2811791FDOQ2811791

Authors: Cécile Gonçalves 

Publication date: 10 June 2016

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

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.

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

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

zbMATH Keywords

algebraic geometrynumber theorycyclic coverpoint counting\(p\)-adic precision

Mathematics Subject Classification ID

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

Cited In (5)

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

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)