1
$\begingroup$

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/. Elliptic curve with equation y^2 = x^3 + 2x + 2 mod(23), which shows 20 points

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

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$ – SAI Peregrinus Nov 22 '20 at 2:30
  • $\begingroup$ @SAIPeregrinus nope! The OP wants to learn EC without a book! $\endgroup$ – kelalaka Nov 22 '20 at 8:04
3
$\begingroup$

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),(8,0),(9,\pm 6),(11,\pm 4)\} $$ on the elliptic curve, in addition to the point at infinity, which is the additive identity.

$\endgroup$
3
  • $\begingroup$ Thank you, very clear explanation! $\endgroup$ – Stijn de Vries Nov 22 '20 at 13:02
  • $\begingroup$ you are welcome. you can accept the answer if you wish $\endgroup$ – kodlu Nov 22 '20 at 14:54
  • $\begingroup$ Sorry, totally forgotten! Thanks! $\endgroup$ – Stijn de Vries Nov 22 '20 at 16:10

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.