Average/approximate difference in value between valid consecutive $x$ coordinates in ECC?

From my basic understanding not all values of $x$ coordinates can satisfy a given elliptic curve equation, i.e. some $x$ coordinate values are not valid points on the curve because $x^3+ax+b$ is not a square.

Therefore, I would like to know what the average/approximate difference $d$ in value between any two valid consecutive $x$-coordinate integers is; if e.g. $x_1$ and $x_2$ are two consecutive valid $x$ coordinate integers on a given curve then in general, what is average/approximate difference value $d = x_2-x_1$?

• $d$ should be pretty close to 2. – CodesInChaos Apr 1 '15 at 9:08

Helmut Hasse proved in his 1936 series of papers "Zur Theorie der abstrakten elliptischen Funktionenkörper" that any elliptic curve $E$ over a finite field $\mathbb F_q$ satisfies the inequality $$\lvert q+1-\#E(\mathbb F_q)\rvert\leq2\sqrt q \text,$$
that is, the number of points is (very) roughly approximated by $q+1$. Since there are almost always (except when $x^3+ax+b=0$) precisely zero or two points corresponding to a given $x$ coordinate, this implies that the points on the curve assume about $(q+1)/2$ different $x$ coordinates. Therefore, the average distance between two "consecutive" (strictly speaking, this is not meaningful without a partial order on $\mathbb F_q$) valid $x$ coordinates is close to $\frac{q+1}{(q+1)/2}=2$.