{
  "id": "1710.03448",
  "version": "v1",
  "published": "2017-10-10T08:42:35.000Z",
  "updated": "2017-10-10T08:42:35.000Z",
  "title": "Improved Complexity Bounds for Counting Points on Hyperelliptic Curves",
  "authors": [
    "Simon Abelard",
    "Pierrick Gaudry",
    "Pierre-Jean Spaenlehauer"
  ],
  "categories": [
    "math.NT",
    "cs.SC",
    "math.AG"
  ],
  "abstract": "We present a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus $g$ defined over $\\mathbb{F}_q$. It is based on the approaches by Schoof and Pila combined with a modeling of the $\\ell$-torsion by structured polynomial systems. Our main result improves on previously known complexity bounds by showing that there exists a constant $c>0$ such that, for any fixed $g$, this algorithm has expected time and space complexity $O((\\log q)^{cg})$ as $q$ grows and the characteristic is large enough.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-10T08:42:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hyperelliptic curve",
      "complexity bounds",
      "counting points",
      "probabilistic las vegas algorithm",
      "local zeta function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}