# addition on finite elliptic curves

I tried to calculate the sum of two Points on an elliptic curve in a finite field. The Curve is defined as following:

$$y^2 \equiv x^3 + x \mod 257$$

So the curve parameters are $a = 1,b = 0,p = 257$.I want to add the two points $P = (1|60)$ and $Q = (15|7)$:

$$60^2 \equiv 1^3 + 1 \equiv 4 \mod 257$$ $$7^2 \equiv 15^3 + 15 \equiv 49 \mod 257$$

To add this two points, I calculate the slope $s$, $x_r$ and $y_r$:

$$s = \frac{y_q - y_p}{x_q - x_p}$$ $$x_r = s^2 - (x_p + x_q)$$ $$y_r = s(x_p - x_r) - y_p$$

for my points $P$ and $Q$ I get:

$$s = \frac{7-60}{15-1} = \frac{-53}{14} = -3.7857142857$$ $$x_r = (\frac{-53}{14})^2 - (1 + 15) = 14.3316326531 - 16 = -1.6683673469$$ $$y_r = \frac{-53}{14}(1-(-1.6683673469)) - 60 = -70.1016763848$$ $$R = (-1.6683673469|-70.1016763848)$$ However: $$x_r^3 + x_r = -6.3121837787$$ while $$y_r^2 = 4914.2450319648$$ So $R$ seems to be outside the curve. Even if I calculate everything modulo 257 I get weird results.

What I don't understand:

• since I defined the curve on a finite field, I expected integer results
• I expected $R$ to be part of the curve
• the definition of $x_r$ is the difference between $s^2$ and the sum of the x-coordinates of the two added points. Why can $s^2$ be interpreted as an x-coordinate or even a length?
• in reference to wikipedia, the addition of two points of an elliptic curve is commutative. That seems to be true for $x_r$, but why should it be true for $y_r$?

Notes:

• I looked for an answer to this questions and all I did find were this and this. Both questions looked similar to mine but I still don't understand addition on elliptic curves.
• I'm really new to elliptic curves, sorry if I did huge mistakes by calculating these values

## 2 Answers

• You are right, when you're working on a finite field, you should get integer results. So let's look at why you aren't.

The problem lies in how you handle the fractions inside the equation, e.g. $s=\frac{y_q-y_p}{x_q-x_p}$. Elliptic curve operations make use of finite field arithmetic. Maybe it'd be easier for you to grasp if you imagined the equation to look like $s=(y_q-y_p)(x_q-x_p)^{-1}\mod p$. This means that you have to calculate the modular inverse of the denominator of your fracture and then multiply this with the nominator.

• $R$ is indeed part of the curve. Recalculate it using the "technique" described above.

• It's not right to see it as length. As you're reducing the result modulo a prime ($\mod p$) the information which you call "length" is lost.

• Take two points that are part of an elliptic curve, e.g. $P$ and $Q$. Commutative means that $P + Q$ gives the same result as $Q + P$. However it does not mean that you can just switch the $x$- and $y$-coordinates

• Thanks for the hint, I will try to calculate the modular inverse :) – Aemyl May 12 '17 at 8:46
• about the cummutative: I didn't want to switch the $x$- and $y$-coordinates, I wondered why I should get the same result by calculating $y_r = s(x_q - x_r) - y_q$ – Aemyl May 12 '17 at 8:49

I don't have enough reputation to comment, so will do so here.

Re commutativity: geometrically, when you add two (unequal) points on an elliptic curve, you draw a secant line through the two points and find the point where it intersects. Then reflect this point across the x-axis to get the sum.

But two points determine a line, so it doesn't matter whether you do $P + Q$ or $Q+P$; the secant line is the same either way.

Algebraically, you correctly note that under exchange of $P$ and $Q$, $x_r$ doesn't change. The same is true for $y_r$. Swapping the points gives you $y_r = s(x_q - x_r) - y_q$. If you expand this polynomial (substitute the full expression for $s$), you'll get the same $y_r$ as before.

• good point, I referred to the algebraic way. I understood that $y_r = s(x_q - x_r) - y_q$ gives the same result, I just wondered why it does. At least I could fix the calculation of $s$, now I get the correct results :) – Aemyl May 12 '17 at 16:34