{
  "id": "1806.05834",
  "version": "v1",
  "published": "2018-06-15T07:25:24.000Z",
  "updated": "2018-06-15T07:25:24.000Z",
  "title": "Counting points on genus-3 hyperelliptic curves with explicit real multiplication",
  "authors": [
    "Simon Abelard",
    "Pierrick Gaudry",
    "Pierre-Jean Spaenlehauer"
  ],
  "comment": "To appear in the proceedings of the ANTS-XIII conference (Thirteenth Algorithmic Number Theory Symposium)",
  "categories": [
    "math.NT",
    "cs.SC",
    "math.AG"
  ],
  "abstract": "We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperelliptic curve defined over a finite field $\\mathbb F_q$, with explicit real multiplication by an order $\\mathbb Z[\\eta]$ in a totally real cubic field. Our main result states that this algorithm requires an expected number of $\\widetilde O((\\log q)^6)$ bit-operations, where the constant in the $\\widetilde O()$ depends on the ring $\\mathbb Z[\\eta]$ and on the degrees of polynomials representing the endomorphism $\\eta$. As a proof-of-concept, we compute the zeta function of a curve defined over a 64-bit prime field, with explicit real multiplication by $\\mathbb Z[2\\cos(2\\pi/7)]$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-15T07:25:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "explicit real multiplication",
      "hyperelliptic curve",
      "counting points",
      "zeta function",
      "las vegas probabilistic algorithm"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}