Problem on Elliptic Curve Point Doubling

Question

Given an elliptical curve e.g. from “Understanding Cryptography” by Parr & Pelzl §9.2 Example 9.5:

$y^2 = x^3 + 2x + 2~~~~ mod~17$

And given a primitive $P = (5, 1)$, the book indicates:

We compute now all the "powers" of P.

They then provide a table:

$2P = (5, 1) + (5, 1) = (6, 3)$

$3P = 2P + P = (10, 6)$

$...$

$18P = (5, 16)$

Unfortunately it is not apparent to me what action they are performing with the addition ($+$), or what they mean by "powers". What operation is being performed to go from $(5, 1) + (5, 1)$ to $(6, 3)$, and so on?

The obvious operation (i.e. what Wolfram alpha does) of $(5, 1) + (5, 1) = (5 + 5, 1 + 1)$ yields $(10, 2)$. There are a plethora of other possible combinations of operations that one could try, but I'd just be guessing.

Generally, given the secret, ordinarily labeled $d$, how ought one calculate $dP = P + P~ +~ ... ~+~ P$?

(This presumably computes the public key $X$ & $Y$ points, from $d$ and the $Gx$ and $Gy$ parameters)

While it is a rather core operation, and likely quite basic, I have found no illustrative examples and at-best convoluted implementations. I'll keep looking, but I thought that a good answer might be a useful for the next person searching.

Edit

This exact example also appears and is discussed at: https://math.stackexchange.com/questions/430836

Answer 1

The point addition $P+Q$ and doubling $2P = P +P $ in Elliptic Curves $E$ are not just x,y coordinates in the Euclidean Plane that you can add the coordinates. One can find the rules in Wikipedia;

Point addition: With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.

Point doubling: Where the points P and Q, are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through P and Q, so the operation is closed using limiting case, the tangent to the curve, E, at P and Q.

---

Given the Elliptic curve $E:y^2= x^3+a x + b$ and a point $P=(x_p,y_p)$ on the curve, the doubling $R=2P = P + P$ can be calculated by:

\begin{align} \lambda &= \frac{3 x_p^2 + a }{2 y_p}\\ x_r &= \lambda^2 -2 x_p\\ y_r &= \lambda(x_p-x_r) - y_p \end{align}

The curve is defined in modular arithmetic $\pmod{17}$, therefore convert $1/2$ into $2^{-1} \equiv 9 \bmod 17$ and find the inverse by extended GCD algorithm.

$\lambda = (3\cdot 5^2 +2)\cdot 9) \equiv 13 \bmod 17$

$x_r = \lambda^2 - 2 x_p = (13^2 -10 ) \equiv 6 \bmod 17 $

$x_y = \lambda(x_p - x_r)-y_p = 13 \cdot ( 1 - 6) - 1 \equiv 3 \bmod 17$

$$(5,1) + (5,1) = (6,3)$$