# 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? Nov 22, 2020 at 2:30
• @SAIPeregrinus nope! The OP wants to learn EC without a book! 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! Nov 22, 2020 at 13:02
• you are welcome. you can accept the answer if you wish Nov 22, 2020 at 14:54
• Sorry, totally forgotten! Thanks! 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? Apr 10 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 Apr 10 at 17:56