{
  "id": "1106.0661",
  "version": "v1",
  "published": "2011-06-03T14:44:58.000Z",
  "updated": "2011-06-03T14:44:58.000Z",
  "title": "Counting Points on Genus 2 Curves with Real Multiplication",
  "authors": [
    "Pierrick Gaudry",
    "David Kohel",
    "Benjamin Smith"
  ],
  "categories": [
    "math.NT"
  ],
  "abstract": "We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field (\\F_{q}) of large characteristic from (\\widetilde{O}(\\log^8 q)) to (\\widetilde{O}(\\log^5 q)). Using our algorithm we compute a 256-bit prime-order Jacobian, suitable for cryptographic applications, and also the order of a 1024-bit Jacobian.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-06-03T14:44:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "counting points",
      "efficiently computable real multiplication endomorphism",
      "finite field",
      "cryptographic applications",
      "accelerated schoof-type point-counting algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1106.0661G"
    }
  }
}