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