{
  "id": "1404.0399",
  "version": "v2",
  "published": "2014-04-01T21:11:30.000Z",
  "updated": "2014-11-29T00:20:55.000Z",
  "title": "On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average",
  "authors": [
    "Igor E. Shparlinski",
    "Andrew V. Sutherland"
  ],
  "comment": "20 pages",
  "categories": [
    "math.NT"
  ],
  "abstract": "For an elliptic curve E/Q without complex multiplication we study the distribution of Atkin and Elkies primes l, on average, over all good reductions of E modulo primes p. We show that, under the Generalized Riemann Hypothesis, for almost all primes p there are enough small Elkies primes l to ensure that the Schoof-Elkies-Atkin point-counting algorithm runs in (log p)^(4+o(1)) expected time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-01T21:11:30.000Z",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-11-29T00:20:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11Y16",
      "11G05",
      "11G07",
      "11L40",
      "11Y16"
    ],
    "keywords": [
      "distribution",
      "reductions",
      "elliptic curve e/q",
      "small elkies primes",
      "schoof-elkies-atkin point-counting algorithm runs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.0399S"
    }
  }
}