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

1 Answer 1

4
$\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),(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.

$\endgroup$
5
  • $\begingroup$ Thank you, very clear explanation! $\endgroup$ Nov 22, 2020 at 13:02
  • $\begingroup$ you are welcome. you can accept the answer if you wish $\endgroup$
    – kodlu
    Nov 22, 2020 at 14:54
  • $\begingroup$ Sorry, totally forgotten! Thanks! $\endgroup$ Nov 22, 2020 at 16:10
  • 1
    $\begingroup$ @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? $\endgroup$
    – dassd
    Apr 10, 2023 at 16:48
  • $\begingroup$ Sorry, I missed those will fix the answer, in fact (7,5) being there means (7,-5)=(7,8) is also there, etc $\endgroup$
    – kodlu
    Apr 10, 2023 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.