3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – fgrieu Dec 9 '19 at 9:10
  • $\begingroup$ @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). $\endgroup$ – fkraiem Dec 9 '19 at 13:31
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sandstar Dec 9 '19 at 16:50
  • $\begingroup$ @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. $\endgroup$ – fkraiem Dec 9 '19 at 16:54
  • $\begingroup$ 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'$? $\endgroup$ – Sandstar Dec 9 '19 at 16:59
  • 1
    $\begingroup$ 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. $\endgroup$ – fkraiem Dec 9 '19 at 17:02
  • $\begingroup$ By the way, there are no "negative" values in finite fields. $\endgroup$ – fkraiem Dec 9 '19 at 17:05
2
$\begingroup$

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 = quadratic_residues(17)
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]
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What if $y = 0$? $\endgroup$ – fkraiem Dec 8 '19 at 22:12
  • $\begingroup$ @fkraiem corrected, thanks. $\endgroup$ – kelalaka Dec 9 '19 at 8:15

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.