2
$\begingroup$

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$?

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

Here's a justification for the estimate in CodesinChaos' comment.

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.