# Bound for Number of $\mathbb{F}_q$-rational points on an elliptic curve

Suppose $p>2$ be a prime and $q=p^e$ for some integer $e$ and $f(x) \in \Bbb F_q[x]$.

i) Show that the roots of the equation $1‎\pm‎ f^\frac{q-1}{2} =0$ in $\Bbb F_q$ are multiple root of the equation $R(x) = 2f(x)(1 \pm f^\frac{q-1}{2})+ f^\prime (x) (x^q-x)$.

ii) Then conclude the number $N_q$ that representing the number of $\Bbb F_q$-rational points on the curve $E: y^2= x^3+ax+b$ where $a,b \in \Bbb F_q$, is in the equation $|N_q - q|\leq‎ \dfrac{q+3}{2}‎$ applies. Any suggestion would be appreciated.

1. If $R(x)=2f(x)\left(1-f(x)^{(q-1)/2}\right)+f'(x)(x^q-x)$ show that $$R'(x)=2f'(x)\left(1-f(x)^{(q-1)/2}\right)+f''(x)(x^q-x).$$ Conclude that if $x_0\in\Bbb{F}_q$ is such that $f(x_0)^{(q-1)/2}=1$ then $R(x_0)=R'(x_0)=0$.
2. Warning: Unless I made a mistake you really want to study (with upper/lower signs matching) $$R_{\pm}(x):=2f(x)(1\mp f(x)^{(q-1)/2})\pm f'(x)(x^q-x).$$
3. Recall that $y^2=z\in\Bbb{F}_q$ has two solutions $y\in\Bbb{F}_q$, when $z^{(q-1)/2}=1$, no solutions when $z^{(q-1)/2}=-1$ and a single solution when $z=0$. Also recall that exactly one of these cases occurs for all $z$.
4. Apply all of the above with $z=x^3+ax+b=f(x)$. The choices of $x$ that give two solutions for $y$ are double roots of $R_+$ and the choices of $x$ that give no solutions for $y$ are double roots of $R_-$. Give upper bounds to the number of choices resulting in either situation by studying the degrees of $R_{\pm}$.
• @ Jyrki Lahtonen: The degree of $R(x)$ is $3/2(q-1)$. Is this true? It is useful? – Masoud May 27 '17 at 11:51
• You get (I stopped after that point) by simple counting $$N_q\le \deg f(x)+\deg R(x).$$ Actually I'm no longer sure about the lower bound, nor about the constant! Anyway the $\pm$ variants are kind of complementary to each other. If $g$ is a fixed non-square of $\Bbb{F}_q$, the equations $y^2=f(x)$ and $y^2=gf(x)$ have exactly $2q$ solutions between them. So any upper bound to $N_q-q$ comes together with a loweer bound. – Jyrki Lahtonen May 27 '17 at 14:31