# Elliptic curve operations for incredulous

[Wikipedia](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) and other materials typically hide all the intermediate steps, so we have to derive them ourseleves to understand how it works under the hood.

## Point addition

$P + Q + R = 0\ where\ P\ne Q\ne R$

Curve equation (Weierstrass form):
$y^2 = x^3 + ax + b$

Our line defined by $P$ and $Q$:
$y = \lambda x + \beta$

Let's go:
$\lambda^2x^2 + 2\lambda x + \beta^2 = x^3 + ax + b$
$x^3 - \lambda^2x^2 + (a - 2\lambda)x + (b - \beta^2) = 0$

Roots of cubic polynomial $ax^3 + bx^2 + cx + d$ (Vieta's theorem):
$p + q + r = - b/a$
$pq + qr + rp = c/a$
$pqr = - d/a$

So in our case:
$x_p + x_q + x_r = - (- \lambda^2) = \lambda^2$
$x_r = \lambda^2 - x_p - x_q$

Where:
$\lambda = \dfrac{y_q - y_p}{x_q-x_p}$

Picking the $y$ that is not on the line:
$\beta = y_p - \lambda x_p$
$y_r = -(\lambda x_r + \beta)$
$y_r = \lambda (x_p - x_r) - y_p$

Reference implementation: https://github.com/ethereum/py_pairing/blob/e95dece17e5d948e62b1492b05ba88b726aa25e6/py_ecc/bn128/bn128_curve.py#L46

NOTE that this also works for cases when either $P$ or $Q$ are tangent points.

### In projective coordinates

Context https://hackmd.io/@cailynyongyong/HkuoMtz6o#Projective-Coordinates

Goal: avoid modular division (finding multiplicative inverse).

Curve equation in projective space:
$y^2z=x^3 + axz^2 + bz^3$

Point transformation:
$P' = (x_p',y_p',z_p) = (x_pz, y_pz, z)$
$Q' = (x_q',y_q',z_q) = (x_qz, y_qz, z)$

Upon conversion from Affine coordinates $z = 1$, but then it can change.

Trick: transform $y_r, x_r$ into fractions having the same denominator, which is effectively $z_r$.

Let's convert our prior addition formulas from affine to projective space:
$\lambda = \dfrac{y_q-y_p}{x_q-x_p} = \dfrac{y_q'/z_q - y_p'/z_p}{x_q'/z_q - x_p'/z_p} = \dfrac{y_q'z_p - y_p'z_q}{x_q'z_p - x_p'z_q}$

Calculating intermediate results:
$u_q = y_q'z_p$
$u_p = y_p'z_q$
$v_q = x_q'z_p$
$v_p = x_p'z_q$
$u = u_q - u_p$
$v = v_q - v_p$
$w = z_pz_q$
$\lambda = u/v$

Now let's expand and simplify:
$x_r = \lambda^2 - x_p - x_q = \dfrac{u^2}{v^2} - x_p'/z_p - x_q'/z_q = \dfrac{u^2w - v^2(v_p + v_q)}{v^2w}$
$y_r = \lambda (x_p - x_r) - y_p = \dfrac{u}{v}(x_p'/z_p - x_r) - y_p'/z_p = \dfrac{uv(v_p - x_rw) - v^2u_p}{v^2w}$

Making substitutions and converging to the same denominator:
$y_r = \dfrac{uv^2v_p - u^2w + v^2(v_p+v_q) - v^3u_p}{v^3w}$
$x_r = \dfrac{u^2wv - v^3(v_p + v_q)}{v^3w}$

Also recalling that:
$x_r = x_r'/z_r$ and $y_r = y_r'/z_r$

It means that:
$x_r' = v(u^2w - v^2(v_p + v_q))$
$y_r' = v^2(uv_p - vu_p) - (u^2w - v^2(v_p+v_q))$
$z_r = v^3w$

Simplifying further:
$t = u^2w - v^2(v_p + v_q)$
$x_r' = vt$
$y_r' = v^2(uv_p - vu_p) - t$
$z_r = v^3w$

NOTE that you might find different letters/representations in various places, the main idea is to minimize the total number of additions/multiplications and reuse intermediate results as much as possible.

### In Jacobian coordinates

### In quadratic extension

## Point doubling

$P + Q + R = 0\ where\ P == Q\ is\ a\ tangent\ point$

Rewriting our curve equation as a function of two variables:
$f(x,y) = y^2 - x^3 - ax - b$

The slope of the tangent is $dy/dx$, but we will use implicit differentiation since our function is defined as $f(x, y) = 0$:
$dy/dx = -\dfrac{df/dx}{df/dy}$

Applying chain rule:
$dy/dx = -\dfrac{-3x^2 - a}{2y}$

Evaluating at the known point:
$\lambda = \dfrac{3x_p + a}{2y_p}$

Then we can reuse formulas obtained previously:
$x_r = \lambda^2 - 2x_p$
$y_r = \lambda (x_p - x_r) - y_p$

Reference implementation: https://github.com/ethereum/py_pairing/blob/e95dece17e5d948e62b1492b05ba88b726aa25e6/py_ecc/bn128/bn128_curve.py#L38

### In projective coordinates

How we can determine that $P = Q$ or $P+Q=O$ in projective coordinates?

Instead of checking that $x_p'/z_p=x_q'/z_q$ and $y_p'/z_p = y_q'/z_q$ we can cross multiply and get:
$x_q'z_p-x_p'z_q=v=0$
$y_q'z_p-y_p'z_q=u=0$ for the case $P=Q$
$y_q'z_p+y_p'z_q=u_q+u_p=0$ for the case $P+Q=O$

Now let's adapt doubling formulas for the projective space:
$\lambda = \dfrac{3x_p + a}{2y_p} = \dfrac{3x_p'/z_p + a}{2y_p'/z_p} = \dfrac{3x_p' + az_p}{2y_p'}$
$u = (3x_p' + az_p)z_p$
$v = 2y_p'z_p$
$\lambda = \dfrac{u}{v}$

We have additionally multiplied by $z_p$ so that later we can have a common denominator:
$x_r = \lambda^2 - 2x_p = \dfrac{u^2 - 2x_p'4y_p'^2z_p}{v^2} = \dfrac{u^2 - 2x_p'y_p'v}{v^2}$
$t = 2x_p'y_p'v$
$s = u^2 - t$

After replacements and adjustments:
$x_r = \dfrac{vs}{v^3}$
$y_r = \lambda (x_p - x_r) - y_p = \dfrac{ux_p'}{vz_p} - \dfrac{us}{v^3} - \dfrac{y_p'}{z_p} = \dfrac{2uvx_p'y_p' - us - 2v^2y_p'^2}{v^3} = \dfrac{u(t - s) - 2v^2y_p'^2}{v^3}$

Therefore:
$x_r'=vs$
$y_r'=u(t-s) - 2v^2y_p'^2$
$z_r=v^3$

## Twist

Frobenius endomorphism = maps every element to it's $p$-th power

||Non-invertible|Invertible|
|-|-|-|
|Structure-preserving mapping (function)|[Homo]morphism|Isomorphism|
| Morphism of an object to itself |Endomorphism|Automorphism|