Affine Addition

One of the key properties of an elliptic curve is that it is possible to define a group law on the set of its points such that the point at infinity serves as the neutral element, and inverses are reflections on the x-axis. The origin of this law can be understood in a geometric picture and is known as the chord-and-tangent rule.

Algebraic definition of the chord-and-tangent rule:

• The point at infinity $O$ is the neutral element.

• The inverse of $O$ is $O$. For any other curve point $(x, y) ∈ E(F) \backslash \{O\}$, the inverse is given by $(x, −y)$. If P is a point on a Short Weierstrass curve with P = (x, 0) then P is called self-inverse.

• For any two curve points $P, Q ∈ E(F)$, the group law is defined by one of the following cases:

1. (Neutral element) If $Q = O$, then the group law is defined as $P + Q = P$

2. (Inverse elements) If $P = (x, y)$ and $Q = (x, −y)$, the group law is defined as $P + Q = O$.

3. (Tangent Rule) If $P = (x, y)$ with $y \neq 0$, the group law $P + P = (x', y')$ is defined as follows:

$$x' = \Big(\frac{3x^2 + a}{2y}\Big)^2 - 2x \\ y' = \Big(\frac{3x^2 + a}{2y}\Big)(x-x') - y$$

1. (Chord Rule) If $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ such that $x_1 \neq x_2$, the group law $R = P + Q$ with $R = (x_3, y_3)$ is defined as follows:

$$x_3 = \Big(\frac{y_2-y_1}{x_2-x_1}\Big)^2 - x_1 - x_2 \\ y_3 = \Big(\frac{y_2-y_1}{x_2-x_1}\Big)(x_1 - x_3) - y_1$$

It is very efficient to compute inverses on elliptic curves. However, computing the addition of elliptic curve points in the affine representation needs to consider many cases, and involves extensive finite field divisions. For point addition, we would need 1 division, 2 multiplications, 1 squaring, and 6 additions on finite fields.

In finite field, computing division is expensive and requires Extended Euclidean Theorem. Computing the division consumes ~$λ$ (e.g., 254) operations, which are several orders of magnitudes larger than remaining computations (e.g., multiplications and additions).

Sage example:

# Tiny JubJub
F13 = GF(13)
a = F13(8)
b = F13(8)
TJJ = EllipticCurve(F13,[a,b])

def add(p, q):
    # we assume that (0, 1) is a neutral element
    O = (0, 1)
    
    if p == O:
        return q
    if q == O:
        return p
    
    if p[0] == q[0] and p[1] == -q[1]:
        return O
    
    if p == q:
        k = (3 * p[0]**2 + a) / (2*p[1])
        x = k**2 - 2 * p[0]
        y = k * (p[0] - x) - p[1]
        return (x, y)
    
    k = (q[1] - p[1]) / (q[0] - p[0])
    x = k ** 2 - p[0] - q[0]
    y = k * (p[0] - x) - p[1]
    return (x, y)
    
def to_affine(p):
    if p == TJJ(0):
        return (0, 1)
    return p.xy()

p = TJJ.random_element()
q = TJJ.random_element()
print(to_affine(p + q))
print(add(to_affine(p), to_affine(q)))