# Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

I am struggling to prove this claim:

I proved that the map $$x\mapsto x^3+1$$ is a bijection from $$\mathbb{F}_p$$ to itself if we have that $$p\equiv 2\bmod{3}$$. We have to use this fact to prove that the elliptic curve $$E:y^2=x^3+1$$ over $$\mathbb{F}_p$$ contains precisely $$p+1$$ points.

I don't understand how many points will be on the curve. For each value of $$x\in\{0,1,2,\ldots,p-1\}$$ we will get a distinct result after computing $$x^3+1$$. But how does that tell me how many points will be on the curve?

For each point it can be paired with either two or zero $$y$$ values, right? But I don't know how many squares there are that are less than $$p$$.

I ask either for help explaining this, or ideally resources I could use to understand the theory behind this so that I can solve it myself.

• "squares there are that are less than $p$" is immaterial, and not defined when working in the field modulo $p$, as we are. The right line of reasoning is: for each $y$ in this field, how many $x$ in this field are there such that $(x,y)$ is the coordinates of a point on the curve? Are these points distinct? Are there other points that we need to count? – fgrieu Dec 9 '19 at 9:10
• @fgrieu You can also do it the other way, for every $x$, count the $y$s, as in the other answer. It's a bit messier however since you have to case-distinguish based on whether $x^3+1$ is a quadratic residue or non-residue or zero (and know a bit about residuosity). – fkraiem Dec 9 '19 at 13:31

For every $$y \in \mathbf F_p$$, there is a unique $$x \in \mathbf F_p$$ such that $$(x,y)$$ is on the curve, namely $$x = \phi^{-1}(y^2)$$, where $$\phi : x \mapsto x^3+1$$. Adding the point at infinity, that gives $$p+1$$ points.

• So, for each $y\in\mathbb{F}_p$ we have that $y^2$ is some other value in the same field. And since our map $\phi$ is bijective, we will find a unique $x$ that it can be paired with so that it lies on our elliptic curve. And that gives us $p$ points, then we add the point at infinity. I understand you correvctly, right? But what about $-y$, won't we have that $(x,-y)$ is on the curve for every $(x,y)$? Won't that give us $2p+1$ points? – Sandstar Dec 9 '19 at 16:50
• @Sandstar No because $y$ and $-y$ are different values, so the fact that they are paired with the same $x$ is irrelevant to the argument. – fkraiem Dec 9 '19 at 16:54
• I think I get you. Do we have that $(x,y) = -(x,-y)$? And so for each negative value of $y$, we will find that it is actually equivalent to some other $y'$? – Sandstar Dec 9 '19 at 16:59
• Yes, if $(x,y)$ and $(x,-y)$ are both on the curve, then they are opposite (w.r.t. the curve group operation) since the line through them is vertical. – fkraiem Dec 9 '19 at 17:02
• By the way, there are no "negative" values in finite fields. – fkraiem Dec 9 '19 at 17:05

With the bijection, you proved that for every $$x$$ there is a unique $$x^3+1$$. Now, for modulo an odd prime number $$p$$ the number of QR (quadratic residue) is $$(p + 1)/2$$ by Euler's criterion.

Therefore these are the solutions for $$y^2$$s for your EC. For every $$y$$, $$-y$$ is going to satisfies the equation i.e. if $$(x,y)$$ is a point on the curve than $$(x,-y)$$ is also a point on the curve except $$y=0$$ for which there is only one. This makes $$(p+1)/2-1 = p$$ points and with the addition of $$\mathcal{O}$$-the point on the infinity, the number of points will make $$p+1$$

Below is the SageMath code for the test.

F = GF(17)
E = EllipticCurve(F,[0, 0, 0, 0, 1])
E.cardinality()

for uInt in range(0, 17):
u = F(uInt)
v2 = u^3 + 1
if not v2.is_square():
continue
v = v2.sqrt()
point = E(u, v)
pointOrder = point.order()
print( point, pointOrder)
print( -point, pointOrder)

Q

With the output

((0 : 1 : 1), 3)
((0 : 16 : 1), 3)
((1 : 6 : 1), 9)
((1 : 11 : 1), 9)
((2 : 3 : 1), 6)
((2 : 14 : 1), 6)
((6 : 8 : 1), 18)
((6 : 9 : 1), 18)
((7 : 2 : 1), 9)
((7 : 15 : 1), 9)
((9 : 4 : 1), 18)
((9 : 13 : 1), 18)
((10 : 7 : 1), 18)
((10 : 10 : 1), 18)
((14 : 5 : 1), 9)
((14 : 12 : 1), 9)
((16 : 0 : 1), 2)         ---> -y = y => y=0
((16 : 0 : 1), 2)         --->
[0, 1, 2, 4, 8, 9, 13, 15, 16]

• What if $y = 0$? – fkraiem Dec 8 '19 at 22:12
• @fkraiem corrected, thanks. – kelalaka Dec 9 '19 at 8:15