{
  "id": "1005.4771",
  "version": "v1",
  "published": "2010-05-26T09:56:23.000Z",
  "updated": "2010-05-26T09:56:23.000Z",
  "title": "Pseudorandom Bits From Points on Elliptic Curves",
  "authors": [
    "Reza R. Farashahi",
    "Igor E. Shparlinski"
  ],
  "categories": [
    "math.NT",
    "cs.CR"
  ],
  "abstract": "Let $\\E$ be an elliptic curve over a finite field $\\F_{q}$ of $q$ elements, with $\\gcd(q,6)=1$, given by an affine Weierstra\\ss\\ equation. We also use $x(P)$ to denote the $x$-component of a point $P = (x(P),y(P))\\in \\E$. We estimate character sums of the form $$ \\sum_{n=1}^N \\chi\\(x(nP)x(nQ)\\) \\quad \\text{and}\\quad \\sum_{n_1, \\ldots, n_k=1}^N \\psi\\(\\sum_{j=1}^k c_j x\\(\\(\\prod_{i =1}^j n_i\\) R\\)\\) $$ on average over all $\\F_q$ rational points $P$, $Q$ and $R$ on $\\E$, where $\\chi$ is a quadratic character, $\\psi$ is a nontrivial additive character in $\\F_q$ and $(c_1, \\ldots, c_k)\\in \\F_q^k$ is a non-zero vector. These bounds confirm several recent conjectures of D. Jao, D. Jetchev and R. Venkatesan, related to extracting random bits from various sequences of points on elliptic curves.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-05-26T09:56:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11G05",
      "11T23",
      "14G50",
      "94A60"
    ],
    "keywords": [
      "elliptic curve",
      "pseudorandom bits",
      "estimate character sums",
      "finite field",
      "rational points"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1005.4771F"
    }
  }
}