Vol. 4, No. 1, 2020

Download this article
Download this article For screen
For printing
Recent Volumes
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
 
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 ym = f(x) with m 2 and f [x] any squarefree polynomial of degree d 3, along with a positive integer N. It can compute #X(𝔽p) for all p N not dividing mlc(f)disc(f) in time O(md3Nlog3NloglogN). 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
Milestones
Received: 28 February 2020
Revised: 28 February 2020
Accepted: 29 April 2020
Published: 29 December 2020
Authors
Andrew V. Sutherland
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA
United States