# How are the points in an elliptic curve over the finite field calculated?

For the elliptic curve with equation $$y^2 = x^3 + x + 0 \pmod{13}$$ in the finite field, how are all the points in this curve calculated. See the image below for an example created via https://graui.de/code/elliptic2/.

The above images shows 20 points. How are the coordinates of these points calculated?

• They're just the points where that equation is true. For a simple equation like that high-school algebra is enough. For curves used in crypto it's faster to use linear algebra techniques. Are you stuck on the former, or on the methods used to optimize practical computations? Commented Nov 22, 2020 at 2:30
• @SAIPeregrinus nope! The OP wants to learn EC without a book! Commented Nov 22, 2020 at 8:04

Given $$y^2 = x^3 + x \pmod{13}\quad (1)$$ note that in addition to the point at infinity, the other points are the solutions $$(x,y) \in \mathbb{F}_{13}\times \mathbb{F}_{13}$$ of (1). With algebraic construction we add the point of infinity ($$\{\mathcal O\}$$) to the set of the solutions $$E := \{ (x, y) \in (\mathbb{F}_{13})^2 \mid y^2 = x^3 + x \} \cup \{\mathcal O\}.$$

Since you need to solve (1) for $$y^2$$ this implies that whenever $$(x,y)$$ is a solution so is $$(x,-y).$$ For a small field like this list the squares

$$\begin{array}{c|ccccccc}\hline y & 0 & \pm 1 & \pm 2 & \pm 3 & \pm 4 & \pm 5 &\pm 6\\ \hline y^2 & 0 & 1 & 4 & 9 & 3 & 12 & 10\\ \hline \end{array}$$

and note that everything must be reduced mod 13. So $$-4$$ is actually $$9.$$

Now, whenever $$x^3+x$$ is equal to $$y^2$$ we pick up $$(x,y),(x,-y)$$ as points on the curve. So now prepare the table

$$\begin{array}{c|ccccccccccccccc}\hline x & 0 & 1 & 2 & 3 & 4 & 5 & 6 &7 &8 &9 &10 &11 &12\\ \hline x^3 & 0 & 1 & 8 & 1 & 12 & 8& 8& 5& 5& 1& 12& 5& 12\\ \hline x^3+x & 0^* & 2 & 10^* & 4^* & 3^* & 0^* & 1^* & 12 & 0^*& 10^*& 9& 3^* & 11\\ \hline \end{array}$$ and use the values of $$x$$ corresponding to the marked points to get the points $$E=\{ (0,0),(2,\pm 6),(3,\pm 2),(4,\pm 4),(5,0), (6,\pm 1),(7,\pm 5),(8,0),(9,\pm 6),(10,\pm 3),(11,\pm 4)\}$$ on the elliptic curve, in addition to the point at infinity, which is the additive identity.

• Thank you, very clear explanation! Commented Nov 22, 2020 at 13:02
• you are welcome. you can accept the answer if you wish Commented Nov 22, 2020 at 14:54
• Sorry, totally forgotten! Thanks! Commented Nov 22, 2020 at 16:10
• @kodlu Why don't (7, 5) and (10, 3) fall into the set E? For those points we also have equality between the "left" and "right" sides? Commented Apr 10, 2023 at 16:48
• Sorry, I missed those will fix the answer, in fact (7,5) being there means (7,-5)=(7,8) is also there, etc Commented Apr 10, 2023 at 17:56