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

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)

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.

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)

• 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

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)