Pseudorandom bits from points on elliptic curves

Reza Rezaeian Farashahi*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Let be an elliptic curve over a finite field of elements, with gcd(q, 6)= 1, given by an affine Weierstraß equation. We use x(P) to denote the x-component of a point P = (x(P), y(P)) ε E. We estimate character sums of the form NΣ n=1X(x(nP)x(nQ)) and NΣ n1,...,nk=1Π ( kΣj=1cjx(( jΠ i=1ni)R)) on average over all F qrational points P,Q, and R on E, where X is a quadratic character, φ is a nontrivial additive character in Fq, and (c 1,...,ck) ε F k qis a nonzero vector. These bounds confirm several recent conjectures of Jao, Jetchev, and Venkatesan, related to extracting random bits from various sequences of points on the elliptic curves.

Original languageEnglish
Article number6043877
Pages (from-to)1242-1247
Number of pages6
JournalIEEE Transactions on Information Theory
Issue number2
Publication statusPublished - Feb 2012

Cite this