# Point Addition in Python

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

![Addition of two points on an elliptic curve over a field of real numbers.](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-Lw8wBFM1sTyU6PfTs88%2F-Lw8xyyAuwDMlI_G2CI8%2Fmedia-1170221-point-addition.png?alt=media\&token=2ea11f55-1b0a-42b4-b67d-0388bc81b065)

{% hint style="info" %}
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.
{% endhint %}

![Addition of two points on an elliptic curve over a finite field.](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-LwQ-CBcl3OJlU-eqsTe%2F-LwQ-gzggJLYgwhAlOSK%2Fimage01.gif?alt=media\&token=532644f2-d557-4f7d-aff5-dab042890345)

#### Implementation in Python

<pre class="language-python"><code class="lang-python">from typing import Optional
<strong>
</strong><strong>inf = float("inf")
</strong>
@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
            )
</code></pre>

**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$$&#x20;

![Point at infinity is the third point where the line joining P and Q meets the curve.](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-LwQ4yNHSIREKALCXRw7%2F-LwQ5iw3ztR37a88NXdM%2FECVertical.png?alt=media\&token=7b36ded2-f158-462a-8034-4ba06f3fede4)

We can initialise the point at infinity like this:

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

#### Resources

* [https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture14.pdf](https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture14.pdf)
