# Point addition on an elliptic curve

I have an elliptic curve $y^2 = x^3 + 2x + 2$ over $Z_{17}$. It has order $19$.

I've been given the equation $6\cdot(5, 1) + 6\cdot(0,6)$ and the answer as $(7, 11)$ and I'm unsure how to derive that answer.

I have $6\cdot(5, 1) = (16,13)$ and $6\cdot(0,6)=(0, 11)$ however when I use point addition to add them together I get $(16,13)+(0, 11)=(14,11)$ which isn't even a point on the curve...

Could someone help me identify where and why I've gone wrong?

For further information here's each of the points:

And here's the curve plotted out:

-

Hints:

• Your calculation of $6(5,1) = (16,13)$ is correct.
• Your calculation of $6(0,6) = (0,11)$ is incorrect, you should get $6(0,6) = (3,1)$.

Maybe if you show how you did that calculation, I can spot the issue.

Once you fix that, I verified the author's result is correct, that is:

$$(16,13)+(3,1) = (7,11)$$

Update

• $P = (0,6)$
• $2P = (9,1)$
• $3P = (6,3)$
• $4P = (7,6)$
-
Thanks for this, I'll redo my working for the second one and if I'm still struggling I'll get back to you, if not then I'll accept this. – Peanut Jun 28 '13 at 15:39
@Peanut: Sounds great, I also added an update with some initial calculations, so you can verify as you are doing your calculations. Let me know if you still have issues. Regards – Amzoti Jun 28 '13 at 15:47
Thanks for the hints, just done $2P$ and it's correct so I've got the method right, must have made a silly mistake somewhere. Is there a quick way to do these, or do you just have to work out $P$ then $2P$, then $3P, 4P$ etc or can you say for example point double $2P$ to get $4P$ and skip $3P$? I've just started looking at this topic and have a programming background so have relatively little mathematical knowledge. – Peanut Jun 28 '13 at 15:59
@Peanut: In practice, you want to minimize the number of calculations you do, so yes, always minimize the number as much as is possible. Here, we can do (2P, 2.2P, 2P + 4P), or get to (3P = P + 2P, 2.3P). Clear? We are typically talking huge numbers in real life, so reductions are critical to speed. ALso, you are doing great! Regards – Amzoti Jun 28 '13 at 16:11
+ 1 for great hints, great follow-up, and great patience! – amWhy Jun 29 '13 at 0:05

You can aid (read: double-check) your calculations with the computer, for instance using Sage or Magma. For example, you can use for free the Magma online calculator. The following code defines your curve $E$ over $\mathbb{Z}/17\mathbb{Z}$, and calculates $6\cdot (0,6)$.

g:=GF(17).1;

E:=EllipticCurve([0,0,0,2*g,2*g]);

P:=E![0,6];

6*P;

The output is $[3:1:1]$ which are projective coordinates for the point $(3,1)$, as it should be.

-
Thanks for this, I'll check it out. – Peanut Jul 1 '13 at 12:16