Abstract

We describe the practical implementation of an average polynomial-time algorithm for counting points on superelliptic curves defined over $\mathbb{Q}$ that is substantially faster than previous approaches. Our algorithm takes as input a superelliptic curve $y^m=f\left(x\right)$ with $m\ge 2$ and $f\in \mathbb{Z}\left[x\right]$ any squarefree polynomial of degree $d\ge 3$, along with a positive integer $N$. It can compute $\#X\left({\mathbb{𝔽}}_p\right)$ for all $p\le N$ not dividing $mlc\left(f\right)disc\left(f\right)$ in time $O\left(m{d}^{3}N{log}^{3}NloglogN\right)$. It achieves this by computing the trace of the Cartier–Manin matrix of reductions of $X$. We can also compute the Cartier–Manin matrix itself, which determines the $p$-rank of the Jacobian of $X$ and the numerator of its zeta function modulo $p$.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors