# Problem on Elliptic Curve Point Doubling

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

• Point Doubling – kelalaka Nov 30 '18 at 21:18
• @kelalaka Ahhhh, yes, that makes sense. – Brian M. Hunt Nov 30 '18 at 21:21
• This question has been answered, but it might give some visibility to the next passers-along to keep this around, but I'm fine with it being deleted if that's preferred here. – Brian M. Hunt Nov 30 '18 at 21:47
• post your calculation as an answer? – kelalaka Nov 30 '18 at 21:49
• @kelalaka The best answer is probably a link to the math question that is virtually identical. Unfortunately trivial answers are turned into comments 😀 . – Brian M. Hunt Nov 30 '18 at 21:54

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)$$

• The tricky part was the modular inverse i.e. 2^-1 = 9. – Brian M. Hunt Nov 30 '18 at 22:21
• Because it's a Galois field, Fermat's Little Theorem can be used instead of extended GCD. – Brian M. Hunt Dec 1 '18 at 13:41