3
$\begingroup$

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

  • 1
    You might want to change your notation. $\Bbb{Z}_p$ is usually used for the $p$-adic integers.2012-06-06
  • 0
    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.2012-06-06
  • 4
    Could someone explain the downvotes? They seem completely uncalled for.2012-06-06
  • 0
    @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?2012-06-06
  • 0
    @Arturo Magidin: In the comment above, what's the definition for non-singular cubic? (sorry, This is my first course on elliptic curves and I don't know much). I'm not sure I understand what you were trying to say in your first post, it would be great if you could please elaborate. Concerning your 2nd post: I guess what I was trying to do was to have a case where there is significantly more than half $X$ values in $\mathbb{F_p}$ such that $f(X)$ is a quadratic residue.2012-06-06
  • 0
    @user22678: Nonsingular cubic means that it does not have repeated roots. So it will factor (over the algebraic closure) as $(x-a)(x-b)(x-c)$, and when you plug in a value for $x$, you get three different things in the product. Again, this is only a heuristic, not a formal argument. Yes, there can be "more" values that are quadratic residues than values that are not quadratic residues, but for large $p$, the difference turns out to be relatively small: the number of quadratic residues differs from "exactly half" by no more than $\sqrt{p}$, which is comparatively small for $p$ large.2012-06-06
  • 0
    So based on the heuristic given, are the only possible three different points $X$ such that $Y^2=f(X)$ is when $Y=0$ (Assuming it will factor as given by your heuristic)? Or are there cases in general when $Y\neq 0$ that give you $3$ distinct $X$ such that $Y^2=f(X)$? But even if it's true this doesn't matter since as you have pointed out the differences in the number of quadratic and non-quadratic residues will still be relatively small and hence it is roughly reasonable to say that approximately half of the elements in $\mathbb{F_p}$ will produce $f(X)$ where $f(X)$ is a quadratic residue.2012-06-06
  • 2
    @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%.2012-06-06

2 Answers 2

6

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

  • 0
    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".2012-06-06
  • 5
    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}$.2012-06-06
  • 1
    @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?2012-06-06
  • 0
    @Eugene: Well, perhaps you can expand it instead, and note the difference between the *actual* count and the rough guesstimate.2012-06-06
  • 1
    @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...2012-06-06
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$).