Recall from the discussion in Group Theory, we learnt how a generator point can be added to itself repeatedly to generate every element of the group. In this section, we'll understand how to perform this addition, and implement it in Python.

#### The theory behind point addition

To add two points $P$and $Q$ on an elliptic curve, find the third point $R$ where line joining $P$ and $Q$ intersects. This value of $R$ is equal to $-(P+Q)$. Reflecting the point along the X-axis will give us $P+Q$.

To find the coordinates of the third point of intersection, simply calculate the slope between P and Q, and extrapolate it using the general equation of elliptic curve.

#### Implementation in Python

from typing import Optional

inf = float("inf")

@dataclass
class Point:
x: Optional[int]
y: Optional[int]

curve: EllipticCurve

def __post_init__(self):
# Ignore validation for I
if self.x is None and self.y is None:
return

# Encapsulate int coordinates in FieldElement
self.x = FieldElement(self.x, self.curve.field)
self.y = FieldElement(self.y, self.curve.field)

# Verify if the point satisfies the curve equation
if self not in self.curve:
raise ValueError

#################################################################
# Point Addition for Pā or Pā = I   (identity)                  #
#                                                               #
# Formula:                                                      #
#     P + I = P                                                 #
#     I + P = P                                                 #
#################################################################
if self == I:
return other

if other == I:
return self

#################################################################
#                                                               #
# Formula:                                                      #
#     P + (-P) = I                                              #
#     (-P) + P = I                                              #
#################################################################
if self.x == other.x and self.y == (-1 * other.y):
return I

#################################################################
# Point Addition for Xā ā  Xā   (line with slope)                #
#                                                               #
# Formula:                                                      #
#     S = (Yā - Yā) / (Xā - Xā)                                 #
#     Xā = SĀ² - Xā - Xā                                         #
#     Yā = S(Xā - Xā) - Yā                                      #
#################################################################
if self.x != other.x:
x1, x2 = self.x, other.x
y1, y2 = self.y, other.y

s = (y2 - y1) / (x2 - x1)
x3 = s ** 2 - x1 - x2
y3 = s * (x1 - x3) - y1

return Point(
x=x3.value,
y=y3.value,
curve=secp256k1
)

#################################################################
# Point Addition for Pā = Pā   (vertical tangent)               #
#                                                               #
# Formula:                                                      #
#     S = ā                                                     #
#     (Xā, Yā) = I                                              #
#################################################################
if self == other and self.y == inf:
return I

#################################################################
# Point Addition for Pā = Pā   (tangent with slope)             #
#                                                               #
# Formula:                                                      #
#     S = (3XāĀ² + a) / 2Yā         .. ā(YĀ²) = ā(XĀ² + aX + b)    #
#     Xā = SĀ² - 2Xā                                             #
#     Yā = S(Xā - Xā) - Yā                                      #
#################################################################
if self == other:
x1, y1, a = self.x, self.y, self.curve.a

s = (3 * x1 ** 2 + a) / (2 * y1)
x3 = s ** 2 - 2 * x1
y3 = s * (x1 - x3) - y1

return Point(
x=x3.value,
y=y3.value,
curve=secp256k1
)

Point at Infinity

Also known as the identity point, it is the third point where P and Q meet, in the figure below.

$P + (-P) = I$

We can initialise the point at infinity like this:

I = Point(x=None, y=None, curve=secp256k1)

Last updated