Counting points on superelliptic curves in average polynomial time

Abstract: We describe the practical implementation of an average polynomial-time algorithm for counting points on superelliptic curves defined over $\Q$ that is substantially faster than previous approaches. Our algorithm takes as input a superelliptic curves $y^m=f(x)$ with $m\ge 2$ and $f\in \Z[x]$ any squarefree polynomial of degree $d\ge 3$, along with a positive integer $N$. It can compute $\#X(\Fp)$ for all $p\le N$ not dividing $m\lc(f)\disc(f)$ in time $O(md^3 N\log^3 N\log\log N)$. 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$.

algebraic geometrynumber theory

Audience: researchers in the topic

( chat | paper | slides | video )

Comments: The slides used in the pre-recorded video can be found here.

Chairs: Marco Streng and David Kohel

---

Algorithmic Number Theory Symposium (ANTS XIV)

Series comments: Registration is now open. Registration is free but required to access the chat and livestream.

This is a hybrid synchronous/asynchronous conference with several ways to participate.

• Click the "paper" link to view contributed papers and posters (open to all).
• Click the "video" link to view pre-recorded talks of accepted papers (open to all).
  These are 15-20 minutes aimed at a general algorithmic number theory audience.
• Click the "slides" link to view slides used in the pre-recorded video when available (open to all).
• Click the "chat" link to access the chat stream related to the talk or poster before, during, and after the live event (registration required).
• Click the "livestream" button to join the live event when it is taking place (registration required and you must be logged in).
  For accepted papers the audience will be expected to have watched the pre-recorded video and have the paper in front of them.

The invited talks will be recorded and made available via the "video" link after the talk is over. None of the other sessions will be recorded.

---