Computer Science > Computational Geometry
[Submitted on 9 Aug 2014 (v1), last revised 23 Aug 2014 (this version, v2)]
Title:A Point Counting Algorithm for Cyclic Covers of the Projective Line
View PDFAbstract: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 $°{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 $\mathcal{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 \geq 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.
Submission history
From: Cecile Goncalves [view email] [via CCSD proxy][v1] Sat, 9 Aug 2014 13:26:36 UTC (28 KB)
[v2] Sat, 23 Aug 2014 07:16:17 UTC (28 KB)
Current browse context:
cs.CG
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.