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?

  • $\begingroup$ What is $E$? Are you using the same symbol to stand for two different curves? $\endgroup$ – Gerry Myerson Oct 28 '13 at 11:57
  • $\begingroup$ Sorry, type, edited a prime for clarity. The bottom two definitions hold for $E$ and $E'$, although $\tau$ is different for each. $\endgroup$ – user100659 Oct 28 '13 at 11:58
  • $\begingroup$ Doing well here....changed the $d$'s in $E'$ to be the $g$'s they should be! $\endgroup$ – user100659 Oct 28 '13 at 12:03
  • $\begingroup$ It is now! (more characters) $\endgroup$ – user100659 Oct 28 '13 at 12:05
  • 1
    $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Oct 28 '13 at 12:20

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]

  • $\begingroup$ If $y\neq0$ is one solution, then $-y$ is another. $\endgroup$ – Jyrki Lahtonen Oct 28 '13 at 12:29
  • $\begingroup$ 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? $\endgroup$ – user100659 Oct 28 '13 at 12:31
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Oct 28 '13 at 14:26
  • $\begingroup$ Ah yes, you are correct, thank you very much! $\endgroup$ – user100659 Oct 28 '13 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.