The Group Law on E($\mathbb{F}_p$)§

An elliptic curve forms a group iff it has distinct roots; that is, the curve is non-singular. A curve defined by $E: y^2 = x^3 + ax + b$ is non-singular if its determinant $\Delta_E = 4a^3 + 27 b^2 \not\equiv_p 0$.

Point Addition on E($\mathbb{F}_p$)

Given points $P_1, P_2 \in E(\mathbb{F}_p)$, $P_1 + P_2 = P_3$ is defined such that $-P_3$ is the third point of intersection between $\overline{P_1P_2}$ and $E(\mathbb{F}_p)$. If $P_1 = P_2$ then $\overline{P_1P_2}$ is defined to be the tangent line. If the line does not intersect a point on the curve, then $P_3$ is defined to be the point at infinity, $\mathcal{O}$.

Properties:

  • $P + \mathcal{O} = \mathcal{O} + P = P$.
  • $P + -P = \mathcal{O},$ where $ -P = (x, -y)$.
  • $P + (Q + R) = (P + Q) + R$.
  • $P + Q = Q + P$.

Elliptic Curve Addition Theorem

Let $E: y^2 = x^3 + ax + b$ be a non-singular elliptic curve and let $P_1(x_1, y_1), P_2(x_2, y_2) \in E$.

  1. If $P_1 = \mathcal{O}$ then $P_1 + P_2 = P_2$ (and vice versa).

  2. If $x_1 = x_2$ and $y_1 = -y_2$ then $P_1 + P_2 = \mathcal{O}$.

  3. Otherwise,

    $$ \lambda \equiv_p \begin{cases} \frac{y_2 - y_1}{x_2 - x_1} & \text{if}\ P_1 \neq P_2\\ \frac{3x_1^2 + a}{2y_1} & \text{if}\ P_1 = P_2 \end{cases} $$

    Then, $$\begin{align*} P_3(x_3, y_3) :&= P_1 + P_2\\ x_3 &\equiv_p \lambda^2 - x_1 - x_2\\ y_3 &\equiv_p \lambda(x_1 - x_3) - y_1 \end{align*} $$