Elliptic curves over a finite field $\mathbb{F}_p$ where $p$ is prime. 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$?
 A: 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).
A: 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$).
