A Point Counting Algorithm for Cyclic Covers of the Projective Line

2014/08/09 by Gonçalves, Cécile
#Computational Geometry (cs.CG) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1408.2095

Abstract

We present a Kedlaya-style point counting algorithm for cyclic covers y^r = f(x) over a finite field \mathbbF_pⁿ 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 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 ≥ 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.

Related

• Counting points on curves over families in polynomial time
• A point counting algorithm using cohomology with compact support
• Efficient Point-Counting Algorithms for Superelliptic Curves
• Counting points on curves using a map to P¹
• Enumerating places of \mathbf P¹ up to automorphisms of \mathbf P¹ in quasilinear time