Elliptic curves over a finite field $\mathbb{F}_p$ where $p$ is prime.

Question

Let $Y^2=f(X)$ be an Elliptic curve over a finite field $\mathbb{F}_p$ where $f(X)=X^3+aX+b$

In an undergraduate coursebook on an Applied Algebra course it states that "It is plausible to suggest that $f(X)$ will be a quadratic residue for approximately half of all the points $X \in \mathbb{F}_p$."

I know that exactly half of all non-zero elements of $\mathbb{F}_p$ are quadratic residues and hence only half will be of the form $Y^2 = f(X)$ for some quadratic residue $Y$. But how does this imply that $f(X)$ will be a quadratic residue for approximately half of all points $X$ in $\mathbb{F}_p$? Is it not possible to have more than 2 distinct elements (say $3$ elements in this example) $X$ in $\mathbb{F}_p$ such that for some $Y^2$ we have $Y^2 = f(s) = f(t) = f(u)$ for distinct $x,t,u \in \mathbb{F}_p$?

Answer 1

Let $E$ be an elliptic curve over $\Bbb{Q}$ with Weierstrass equation $$ y ^2 = x^3 + Ax +B $$ with $A, B \in \Bbb{Z}$.

Let $a(p) = p + 1 - \#E(\Bbb{F_p})$, where $p$ is prime and $$ E(\Bbb{F_p}) = \{ (x, y \in \Bbb{F}_p^2 \mid (x, y) \in E \} $$

By a theorem of Hasse and Weil (the statement of which can be found in Silverman-Tate's Rational Points on Elliptic Curves pg 110) we have that for every prime $p$, $$ | a(p) | \leq 2 \sqrt{p}. $$

If f(X) is a quadratic residue for half the elements in $\Bbb{F}_p^\times$ (the unit group of $\Bbb{F}_p$) we have that $\#E(p)= p + 1$ (since each residue would give you two solution for y and hence 2 points, and $0$ only gives you one). So we see by Hasse-Weil that the number of points in $E(\Bbb{F_p})$ is $p + 1 + \mbox{error term}$ where $\mbox{error term} \leq 2\sqrt{p}$. Thus it is plausible to guess that $f(X)$ is a residue in $\Bbb{F_p}$ approximately half the time.

However when looking at the actual number of points on an elliptic curve $E$ over a finite field $\Bbb{F_p}$, it is not the case in general. For instance as in this paper (Theorem 2.1) and this paper (Proposition 1 & 2).

Answer 2

Noone is implying what you say...it is a heuristic argument not a proof. The idea is that modulo most $p$, the cubing function permutes the integers mod $p$. Then $f(x) = x^3 + Ax + B$ will "roughly" permute the integers mod $p$ (since it is a sum of the cubing function, the identity function and a constant).

So really we expect to get approximately $\frac{p-1}{2}$ quadratic residues mod $p$ from the values of $f(x)$, since the values appear to be almost random, a rough permutation of the integers mod $p$.

This is probably supposed to be a heuristic argument supporting the outcome of the Hasse bound. The idea is that each time $f(x)$ is a QR mod $p$ we get $2$ values for $y$ (unless $f(x)=0$ in which we get $1$). But our previous argument suggests that roughly $\frac{p-1}{2}$ of the values of $f(x)$ will give quadratic residues. Adding in the point at infinity we expect that $E(\mathbb{F}_p)$ is roughly:

$2(\frac{p-1}{2})+1+1 = p+1$.

The Hasse bound makes this more precise:

$|E(\mathbb{F_p}) - (p+1)| \leq 2\sqrt{p}$

i.e. the "error" cannot be more than $2\sqrt{p}$ in either direction. This result actually works for any finite field (replace $p$ with $q=p^n$).