2

Assume I have these two elliptic curves: \begin{align*} E:Y^2&=X^3+b_2X^2+b_4X+b_6\\ E':Y^2&=X^3+gb_2X^2+g^2b_4X+g^3b_6, \end{align*} over $\mathbb{F}_q$, where $g$ is not a square in $\mathbb{F}_q$, and $\mathbb{F}_q$ does not have characteristic $2$. I know that $\#E(\mathbb{F}_q)=q+1-t$ and am asked to prove that $\#E'(\mathbb{F}_q)=q+1+t$. I am however not really sure how to do this. I know that by definition $\#E(\mathbb{F}_q)=q+1-\tau$ and $\#E(\mathbb{F}_q)=q+1-\pi-\pi'$, where $\pi$ and $\pi'$ are the zeroes of $T^2-\tau T+q$. Any ideas on how I could approach this problem?

user100659
  • 109

1 Answers1

5

I think that the following trick is wanted. Consider the quantities $$ f(X)=X^3+b_2X^2+b_4X+b_6 $$ and $$ h(X')=X'^3+gb_2X'^2+g^2b_4X'+g^3b_6. $$ We see that $g^3f(X)=h(gX)$. Because $g^3$ is a non-square, if we fix the value $X=x\in F_q$ then one and only one of the following alternatives will occur:

  1. We have $h(gx)=f(x)=0$.
  2. $h(gx)$ is a non-zero square, and $f(x)$ is a non-zero non-square.
  3. $h(gx)$ is a non-zero non-square, and $f(x)$ is a non-zero square.

In all cases the equations $$ y^2=h(gx)\qquad\text{and}\qquad y^2=f(x) $$ have exactly two solutions $y\in F_q$ between them. In respective cases 1) one solution $y=0$ to each, 2) two solutions to former, none to the latter, 3) none to the former, two to the latter.

[Edit] Adding more details. Let $q_i,i=1,2,3$ be the number of those elements $x\in \Bbb{F}_q$ such that we are in case $i$. Taking into account the point at infinity we see that the numbers of points on the two curves are $$\begin{aligned} E(\Bbb{F}_q)&=q_1+2q_3+1,\\ E'(\Bbb{F}_q)&=q_1+2q_2+1. \end{aligned}$$ This is because if $x$ is in case 1, then there is one point of the form $(x,0)\in E$, and one point $(gx,0)\in E'$. If $x$ is in case 2, then there are two points of the form $(gx,y)\in E'$ but no points of the form $(x,y)\in E$. And if $x$ is in case 3, then the reverse holds.

The claim follows from this as each $x$ falls into exactly one of the three cases, so $q_1+q_2+q_3=q$. [/Edit]

Jyrki Lahtonen
  • 133,153
  • If $y\neq0$ is one solution, then $-y$ is another. – Jyrki Lahtonen Oct 28 '13 at 12:29
  • This seems to do well. Just one more question. In $\mathbb{F}_q$ there are exactly $\frac{q-1}{2}$ squares and $\frac{q-1}{2}$ non-squares. Thus it seems that the amount of solutions to $h(gx)$ in step $2$ and the amount of solutions to $f(x)$ in step $3$ are equal. Thus we would have that $#E(\mathbb{F}_q)=#E'(\mathbb{F}_q)$. But my question says they are not equal, where does the extra term 2t come from? – user100659 Oct 28 '13 at 12:31
  • No. It does not follow that $#E(F_q)=#E'(F_q)$. The upshot here is that $h(gx)$ is a square if $f(x)$ is not, and vice versa. We can't say anything about how often each case occurs. So $#E(F_q)+#E'(F_q)=2q+2$ is all we get. – Jyrki Lahtonen Oct 28 '13 at 14:26
  • Ah yes, you are correct, thank you very much! – user100659 Oct 28 '13 at 14:38