# 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

### I give a python program to clarify the above answer.

Given the Elliptic curve $$E:y^2= x^3+2 x + 2 \pmod {17} , \#E=19$$ and a primitive point $$P=(x_p,y_p)=(5,1)$$ on the curve. We calculate the $$nP$$
# -*- 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 + 2x + 2 (mod 17)  #E=19
p = 17
a = 2
b = 2
# the primitive point (x1,y1)=(5,1)
x1 = x2 =5
y1 = y2 = 1
print str(1)+"P:\t", (x1, y1)
for i in range(2, 19):
s = 0
if (x1 == x2):
# indentical point
s = ((3 * (x1 ** 2) + a) * modinv(2 * y1, p))%p
else:
# different points
s = ((y2 - y1) * modinv(x2 - x1, p))%p
# calculate i.P
x3 = (s ** 2 - x1 - x2) % p
y3 = (s*(x1 - x3) - y1) % p
print str(i) + "P:\t", (x3,y3)
(x2, y2) = (x3, y3)


Run this program, we can get the result:

1P:     (5, 1)
2P:     (6, 3)
3P:     (10, 6)
4P:     (3, 1)
5P:     (9, 16)
6P:     (16, 13)
7P:     (0, 6)
8P:     (13, 7)
9P:     (7, 6)
10P:    (7, 11)
11P:    (13, 10)
12P:    (0, 11)
13P:    (16, 4)
14P:    (9, 1)
15P:    (3, 16)
16P:    (10, 11)
17P:    (6, 14)
18P:    (5, 16)