The group $E(\mathbb{F}_p)$ has exactly $p+1$ elements

Question

Let $E/\mathbb{F}_p$ the elliptic curve $y^2=x^3+Ax$.

We suppose that $p \geq 7$ and $p \equiv 3 \pmod {4}$.

I want to show that the group $E(\mathbb{F}_p)$ has exactly $p+1$ elements.

I was wondering if we could use the rank of the group.. Do you have an idea?

EDIT:

There are the following possibilities:

If the point $(x,y)$ is in $E(\mathbb{F}_p)$, then the point $(x,-y)$ is also in $E(\mathbb{F}_p)$.

If the point $(-x,y)$ is in $E(\mathbb{F}_p)$, then the point $(-x,-y)$ is also in $E(\mathbb{F}_p)$.

$y^2=f(x)$

$f(x)=x^3+Ax \Rightarrow f(-x)=-f(x)$

Let $(x, y)$ be a point in $E(\mathbb{F}_p)$. Then $f(x)$ is a square. If $(-x, y)$ would also be a point in $E(\mathbb{F}_p)$, then $f(-x)$ would also be a square, and then $-f(x)$ would be a square, so $-1$ would be a square. That cannot be true, since $p \equiv 3 \pmod 4$. Is this correct?

But I still don't understand how we can count the solutions. Could you explain it to me?

Answer 1

Trying to clarify the step that seems to be troubling the OP.

We partition the elements $x\in\Bbb{F}_p$ into three subsets $S_1,S_2$ and $S_3$:

• Subset $S_1$ consists of those elements $x\in\Bbb{F}_p$ such that $x^3+Ax=0$. You should notice that if $x\in S_1$, then $y=0$ is the only solution of $y^2=x^3+Ax$. Therefore to each $x\in S_1$ there is a single point $(x,0)$ on the curve.
• Subset $S_2$ consists of those elements $x\in\Bbb{F}_p$ such that $x^3+Ax$ is a non-zero square in the field $\Bbb{F}_p$. If $x\in S_2$, and $y^2=x^3+Ax$ then $y\neq0$, and $(-y)^2=x^3+Ax$ is also a solution. And the only other solution. Therefore to each $x\in S_2$ there are two points, $(x,y)$ and $(x,-y)$ on the curve.
• Subset $S_3$ consists of those elements $x\in\Bbb{F}_p$ such that $x^3+Ax$ is not a square in the field $\Bbb{F}_p$. So if $x\in S_3$, then there are no solutions $y$ to the equation $y^2=x^3+Ax$.

If we denote by $|S_1|$ (resp. $|S_2|, |S_3|$) the number of elements in each of the three sets, then the number of pairs $(x,y)\in\Bbb{F}_p^2$ such that $y^2=x^3+Ax$ is $$ N=|S_1|+2\cdot |S_2|+0\cdot |S_3|. $$ The key observation is that if $x^3+Ax$ is a non-zero square, then $(-x)^3+A(-x)=-(x^3+Ax)$ is a non-square, for otherwise their ratio $=-1$ would also be a square which is not the case. Therefore if $x\in S_2$, then $-x\in S_3$ and vice versa, if $x\in S_3$, then $-x\in S_2$. This means that $|S_2|=|S_3|$. Thus $2\cdot|S_2|=|S_2|+|S_3|$, so $$ N=|S_1|+|S_2|+|S_3|=|\Bbb{F}_p|=p. $$ Taking into account the point at infinity we see that there are $p+1$ points altogether on your elliptic curve.

Answer 2

For $x=0$ we find the point $(0,0)$.

If $x \neq 0$, we have $f(x) = x^3+Ax = -( (-x)^3 + A(-x) ) = -f(-x)$. If $f(x)=0$ we find the two points $(x,0)$ and $(-x,0)$. If $f(x) \neq 0$ then either $f(x)$ or $-f(x)$ is a square in $\mathbb{F}_p$ (using the fact that $p \equiv 3 \mod 4$) so either we find two points $(x,y)$, $(x,-y)$ or two points $(-x,y)$, $(-x,-y)$. In all cases, we see that there are two points $(a,b)$ on the curve with $a = \pm x$.

In total, this gives us $1 + \frac{p-1}{2} \cdot 2 = p$ points on the curve, which together with the point at infinity gives $\#E(\mathbb{F}_p) = p+1$.