Point Addition in Python
Last updated
Was this helpful?
Last updated
Was this helpful?
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.
To add two points and on an elliptic curve, find the third point where line joining and intersects. This value of is equal to . Reflecting the point along the X-axis will give us .
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
def __add__(self, other):
#################################################################
# 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
#################################################################
# Point Addition for Xā = Xā (additive inverse) #
# #
# 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.
We can initialise the point at infinity like this:
I = Point(x=None, y=None, curve=secp256k1)