{
  "id": "2004.10189",
  "version": "v1",
  "published": "2020-04-21T17:52:57.000Z",
  "updated": "2020-04-21T17:52:57.000Z",
  "title": "Counting points on superelliptic curves in average polynomial time",
  "authors": [
    "Andrew V. Sutherland"
  ],
  "comment": "15 pages",
  "categories": [
    "math.NT",
    "math.AG"
  ],
  "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-21T17:52:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11G40",
      "14G10",
      "14H25",
      "11Y16"
    ],
    "keywords": [
      "superelliptic curves",
      "average polynomial time",
      "counting points",
      "cartier-manin matrix",
      "average polynomial-time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}