# Amount of points on an elliptic curve over $F_q$

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?

• What is $E$? Are you using the same symbol to stand for two different curves? – Gerry Myerson Oct 28 '13 at 11:57
• Sorry, type, edited a prime for clarity. The bottom two definitions hold for $E$ and $E'$, although $\tau$ is different for each. – user100659 Oct 28 '13 at 11:58
• Doing well here....changed the $d$'s in $E'$ to be the $g$'s they should be! – user100659 Oct 28 '13 at 12:03
• It is now! (more characters) – user100659 Oct 28 '13 at 12:05
• It may help to notice that the right side of $E'$ is $(g^3)(U^3+b_2U^2+b_4U+b_6)$, where $U=X/g$. – Gerry Myerson Oct 28 '13 at 12:20

## 1 Answer

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.

 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]

• 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