5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The excellent solution posted by user133281 is a generalization of the stuff in this closely related question. $\endgroup$ – Jyrki Lahtonen Jan 3 '15 at 20:02
  • $\begingroup$ @JyrkiLahtonen $$E(\mathbb{F}_p)=\{(x, y) \in \mathbb{F}_p \times \mathbb{F}_p | y^2=x^3+Ax \} \cup \{\overline{0}\} $$ So $E(\mathbb{F}_p)$ contains the following elements: $(0,0)$, $(x,y) $, $(x,-y) $. Since $p \geq 7$ and $p \equiv 3 \pmod 4$ we have that the elements $(-x,y)$ and $(-x,-y)$ are also in $E(\mathbb{F}_p)$, or am I wrong? But... how can we find the number of elements? $\endgroup$ – evinda Jan 9 '15 at 17:33
  • $\begingroup$ Didn't user133821 already explain this? In the average there is exactly one $y$ to each $x$. This as a consequence of the fact that to a given $x$ there are two $y$s, if and only if to $-x$ there are none. $\endgroup$ – Jyrki Lahtonen Jan 9 '15 at 17:55
  • $\begingroup$ I edited my post.. Could you take a look at it? @JyrkiLahtonen $\endgroup$ – evinda Jan 9 '15 at 20:54
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer!!! Is the fact that $N=|\mathbb{F}_p|$ somehow related with the fact that there are $\frac{p+1}{2}$ quadratic residues modulo $p$ ? $\endgroup$ – evinda Feb 3 '15 at 15:09
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited my post.. Could you take a look at it? $\endgroup$ – evinda Jan 9 '15 at 20:54

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.