#### Vol. 4, No. 1, 2020

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
Counting points on superelliptic curves in average polynomial time

### Andrew V. Sutherland

Vol. 4 (2020), No. 1, 403–422
##### Abstract

We describe the practical implementation of an average polynomial-time algorithm for counting points on superelliptic curves defined over $ℚ$ 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 ℤ\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$.

 In memory of \hrefhttps://en.wikipedia.org/wiki/Peter_Montgomery_(mathematician)Peter L. Montgomery.
##### Keywords
superelliptic curve, Cartier–Manin matrix, Hasse–Witt matrix, average polynomial-time
##### Mathematical Subject Classification 2010
Primary: 11G20
Secondary: 11M38, 11Y16, 14G10