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

-
You might want to change your notation. $\Bbb{Z}_p$ is usually used for the $p$-adic integers. – Eugene Jun 6 '12 at 3:03
Since $f(x)$ is a nonsingular cubic, you expect $f(u)$ to be the product of three distinct values. Assuming (this is just a 'plausibility' argument, not a proof) that these values are evenly distributed, you would have exactly the same number of combinations that give you quadratic residues as those that give you nonresidues: you get quadratic residues if all three are or if exaclty one is a quadratic residue, and you get nonresidues if all three, or exactly one, of the values are nonresidues. There are $(p-1)/2$ of each. – Arturo Magidin Jun 6 '12 at 3:33
Could someone explain the downvotes? They seem completely uncalled for. – Alex B. Jun 6 '12 at 3:34
@user22678: Note that your "is it possible" does not disprove the statement. The statement is not asserting that you will get all quadratic residues, just that you will get quadratic residues approximately half the time. In fact, yes, there are three points for which the value of $f$ is the same: the three roots! (if it factors). But having three points that give you the same quadratic residue.... why would that tell you that you don't get quadratic residues about half the time, and do get them about half the time? – Arturo Magidin Jun 6 '12 at 3:43
@user22678 To reiterate: all that the textbook is saying is A) a random element of $\mathbb{F}_p$ is (almost) as likely to be a QR or a NQR, B) if $X$ is random, then so is $f(X)$. You can think of the Hasse-Weil bound $2\sqrt p$ for the difference as stating that the variance is $\sqrt p$ (common enough for a binomial distribution), and instead of 95% reliability we get 100%. – Jyrki Lahtonen Jun 6 '12 at 7:01

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

-
Yes, but the claim is not that the value will definitely be that, but rather that "it is plausible to suggest" that the count will be approximately half. Theorem 2.1 of the first paper, for instance, gives the number of points as $(p-3)/2$ when $p\equiv 5\pmod{6}$; for large primes, this is indeed, very close to "half". – Arturo Magidin Jun 6 '12 at 3:38
The statement in question is that for approximately half of the values $x \in \mathbb{F}_p$, $f(x)$ is a quadratic residue. You can't disprove this until you make the statement precise. And in fact, it is a reasonable statement in that the error is at most $2\sqrt{p}$. – Pete L. Clark Jun 6 '12 at 3:39
@ArturoMagidin Ah I see that the emphasis is in the plausibility. It is true then that the Hasse-Weil estimate certainly applies. Should I remove my answer then? – Eugene Jun 6 '12 at 3:43
@Eugene: Well, perhaps you can expand it instead, and note the difference between the actual count and the rough guesstimate. – Arturo Magidin Jun 6 '12 at 3:45
@Eugene: I expect that the paragraph in question is in fact a preamble to Hasse-Weil, with Hasse-Weil making that "guesstimate" precise and justifying it... – Arturo Magidin Jun 6 '12 at 4:13

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

-