Clarification about Hasse's Theorem for Elliptic Curve over Finite Fields

Question

In the proof of Hasse's Theorem over finite fields, one considers the Frobenous endomorphism $\phi(x,y) \rightarrow (x^q,y^q) \in E(\bar{F_q})$ and then notes that this endomorphism fixes the elements of $F_q\times F_q$ but permutes the rest of the element of ($\bar{F_q}\times \bar{F_q})\setminus (F_q\times F_q)$. Therefore, $$\#E(F_q) = \#ker(\phi - 1) = deg(\phi - 1)$$

In both Silverman's book as well as Washington's book, they go to extreme lengths (requiring Weil's pairing) in calculating the degree of this endomorphism. My question is, why can't we directly calculate the degree of this endomorphism? In other words, what's wrong with the following argument?

Let's pick a point $(\bar{x},\bar{y}) \in E(\bar{F_q})\setminus E(F_q)$ which will not be fixed by Frobenous. Then $(\bar{x}^q,\bar{y}^q)$ and $(\bar{x},\bar{y})$ cannot be equal. Therefore the explicit formula for the X-coordinate of $(\phi - 1)(\bar{x},\bar{y}) = (\bar{x}^q,\bar{y}^q) \oplus (\bar{x},-\bar{y})$ can be calculated using explicit point addition formula as $$\left(\frac{\bar{y}^q + \bar{y}}{\bar{x}^q - \bar{x}}\right)^2-\bar{x}^q - \bar{x} = \beta$$ for some $\beta \in \bar{F_q}\setminus F_q$ which is the the x-coordiate of some point. The degree of this equation can be easily calculated using high-school algebra, and that should tell us the number of points on the curve.

There is something wrong with my argument or Hasse's theorem won't be a bound. Can someone please point me what's wrong?

Answer 1

Here is a partial answer. The fraction$$(y^q + y)^2/(x^q - x)^2 - x^q - x$$is a rational function in $x$, but of much lower degree than $3q$.

When I tried it for the elliptic curve $y^2 = x^3 - x$ mod $7$, as in the example above, it reduced to an degree $8$ polynomial divided by a degree $7$ polynomial. That exactly agrees with the degree of $\phi - 1$ being $8$.

In general, the degree should tell us how many rational points are on the curve, but I do not see how to obtain this from the rational function. Any $x_0$ in the finite field with $q$ elements for which the corresponding $y$ satisfies $y = 0$ or $y^{q - 1} = -1$ cancels $x - x_0$ from the numerator and denominator and thereby lowers the degree.

But I have not yet been able to turn this into a count of rational points on the curve. I am sure it is possible with the correct insight.

Answer 2

I actually found the answer. Basically in the expression $$\frac{(y^q + y)^2}{(x^q -x)^2} - (x^q + x) = \beta $$ one needs to discard all the roots of $x \in F_q$ since for those values of $x$, $(x^q -x)^2$ in the denominator will end up being zero. (Note that we are not guaranteed that simplifying the above equation will only have roots in $\bar{F}_q \setminus F_q $. This was the main flaw in my original argument.) Therefore, we have to manually discard roots that are in $F_q$.

After discarding those roots, the degree of numerator (or equivalently, the degree of the denominator + 1; +1 for point at infinity) is equal to size of the kernel.

Doing this exercise has helped me understand the motivation for SEA algorithm so much better. Thanks everyone for taking the time to reply to my question.