# 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

• 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 :) 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$ 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 :) May 12 '17 at 16:34

### I write the python program to show the procedure of calculation.

1. Given the Elliptic curve $$E:y^2= x^3+x \pmod {257}, \#P=256$$

and two point $$P=(x_p,y_p)=(1,60)$$, $$Q=(x_q,y_q)=(15,7)$$ on the curve. We calculate the $$P+Q$$

# -*- coding:UTF-8

# Extended Euclidean algorithm
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

# calculate modular inverse
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m

# define the curve E: y^2 = x^3 + x  (mod 257)  #E=256
p = 257
a = 1
b = 0

P=(1, 60)  # point P
Q=(15, 7)  # point Q
def nPlusm(P, Q):
x1 = P[0]
y1 = P[1]
x2 = Q[0]
y2 = Q[1]
s = 0
if (x1 == x2):
s = ((3 * (x1**2) + a) * modinv(2*y1, p))%p
else:
# x1 != x2
s = ((y2-y1) * modinv(x2-x1, p))%p
x3=(s**2 - x1 - x2)%p
y3=(s*(x1-x3) - y1)%p
return (x3, y3)

print "P(1, 60) + Q(15, 7) = %s"%(nPlusm(P, Q), )

2. Run this program, we can get the result:
P(1, 60) + Q(15, 7) = (18, 243)

3. Actually we can add any two points using above program.

Listing all the points here, there are 255 points besides the $$O$$ element.

[(0, 0), (1, 60), (1, 197), (3, 95), (3, 162), (4, 117), (4, 140), (6, 42), (6, 215), (10, 53), (10, 204), (11, 91), (11, 166), (12, 55), (12, 202), (15, 7), (15, 250), (16, 0), (18, 14), (18, 243), (19, 14), (19, 243), (21, 95), (21, 162), (22, 90), (22, 167), (23, 25), (23, 232), (24, 22), (24, 235), (27, 101), (27, 156), (28, 69), (28, 188), (34, 70), (34, 187), (35, 48), (35, 209), (37, 33), (37, 224), (38, 13), (38, 244), (39, 48), (39, 209), (42, 63), (42, 194), (43, 44), (43, 213), (46, 39), (46, 218), (47, 82), (47, 175), (49, 121), (49, 136), (52, 9), (52, 248), (54, 100), (54, 157), (56, 107), (56, 150), (59, 98), (59, 159), (61, 25), (61, 232), (63, 7), (63, 250), (64, 117), (64, 140), (66, 39), (66, 218), (67, 59), (67, 198), (68, 73), (68, 184), (70, 80), (70, 177), (73, 121), (73, 136), (74, 3), (74, 254), (75, 124), (75, 133), (77, 101), (77, 156), (78, 112), (78, 145), (80, 81), (80, 176), (81, 118), (81, 139), (82, 106), (82, 151), (84, 114), (84, 143), (86, 18), (86, 239), (88, 32), (88, 225), (92, 29), (92, 228), (95, 115), (95, 142), (99, 123), (99, 134), (100, 65), (100, 192), (101, 54), (101, 203), (102, 97), (102, 160), (104, 74), (104, 183), (106, 21), (106, 236), (107, 51), (107, 206), (112, 110), (112, 147), (115, 8), (115, 249), (119, 30), (119, 227), (120, 56), (120, 201), (122, 120), (122, 137), (125, 43), (125, 214), (132, 83), (132, 174), (135, 121), (135, 136), (137, 125), (137, 132), (138, 34), (138, 223), (142, 128), (142, 129), (145, 39), (145, 218), (150, 45), (150, 212), (151, 79), (151, 178), (153, 101), (153, 156), (155, 10), (155, 247), (156, 93), (156, 164), (157, 12), (157, 245), (158, 88), (158, 169), (162, 41), (162, 216), (165, 50), (165, 207), (169, 2), (169, 255), (171, 31), (171, 226), (173, 25), (173, 232), (175, 103), (175, 154), (176, 89), (176, 168), (177, 11), (177, 246), (179, 7), (179, 250), (180, 74), (180, 183), (182, 72), (182, 185), (183, 48), (183, 209), (184, 120), (184, 137), (187, 5), (187, 252), (189, 117), (189, 140), (190, 84), (190, 173), (191, 110), (191, 147), (193, 73), (193, 184), (194, 112), (194, 145), (196, 114), (196, 143), (198, 26), (198, 231), (201, 87), (201, 170), (203, 58), (203, 199), (205, 113), (205, 144), (208, 120), (208, 137), (210, 27), (210, 230), (211, 110), (211, 147), (214, 67), (214, 190), (215, 20), (215, 237), (218, 3), (218, 254), (219, 49), (219, 208), (220, 14), (220, 243), (222, 3), (222, 254), (223, 92), (223, 165), (229, 76), (229, 181), (230, 74), (230, 183), (233, 95), (233, 162), (234, 114), (234, 143), (235, 102), (235, 155), (236, 22), (236, 235), (238, 33), (238, 224), (239, 33), (239, 224), (241, 0), (242, 112), (242, 145), (245, 109), (245, 148), (246, 86), (246, 171), (247, 77), (247, 180), (251, 99), (251, 158), (253, 73), (253, 184), (254, 22), (254, 235), (256, 68), (256, 189)]

4. the modinv function is taken from here.

https://gist.github.com/ssanin82/0b55a730ddbc7dafa94d