Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
