Why does elliptic curve point addition satisfy the associative law?

This article introduces the proof of the associativity law for elliptic curve point addition, as well as the stronger 9-point theorem. Additionally, it covers three corollaries of this theorem: Pascal's theorem, Pappus' theorem, and the polar principle of pole and polar for conic sections.

Elementary Proof

(Theorem 1:) For a non-singular elliptic curve $E:y^2=x^3+Ax+B$, take three distinct points $P,Q,R$ such that the sum of any two or three points is not the point at infinity $\mathcal{O}$. Define $P+Q$ as the third intersection point of the line connecting $P$ and $Q$ with $E$, reflected about the $x$-axis (this point clearly lies on $E$). Then we have:

$$(P+Q)+R=P+(Q+R)$$

(Proof 1:) We attempt to prove this using a relatively elementary method. Let the coordinates of the three points $P,Q,R$ on $E$ be $(x_1,y_1),(x_2,y_2),(x_3,y_3)$. Define ${\lambda }_{ab}=\frac{y_b-y_a}{x_b-x_a}$:

$$P+Q=({\lambda }_{12}^2-x_1-x_2,-{\lambda }_{12}(({\lambda }_{12}^2-x_1-x_2)-x_1)-y_1)$$

Denote this point as $S(x_s,y_s)$;

$$Q+R=({\lambda }_{23}^2-x_2-x_3,-{\lambda }_{23}(({\lambda }_{23}^2-x_2-x_3)-x_2)-y_2)$$

Denote this point as $T(x_t,y_t)$.

Then compute:

$$x_{(P+Q)+R}={\lambda }_{s3}^2-x_s-x_3$$$$x_{P+(Q+R)}={\lambda }_{1t}^2-x_1-x_t$$

Then verify that $x_{(P+Q)+R}=x_{P+(Q+R)}$. Since manual calculation is quite tedious, we use Sagemath's Gröbner basis reduction to verify that the difference is $0$.

# 1) Base polynomial ring and fraction field
R = PolynomialRing(QQ, ['A','B','x1','y1','x2','y2','x3','y3'], order='lex')
A,B,x1,y1,x2,y2,x3,y3 = R.gens()
K = R.fraction_field()

# 2) Addition formulas (x- and y-coordinate) using secant/slope; generic position
def xAdd(xa, ya, xb, yb):
    lam_ab = (yb - ya)/(xb - xa)
    return lam_ab**2 - xa - xb

def yAdd(xa, ya, xb, yb):
    lam_ab = (yb - ya)/(xb - xa)
    return -lam_ab*((lam_ab**2 - xa - xb) - xa) - ya

# 3) Lift symbols to fraction field
A,B,x1,y1,x2,y2,x3,y3 = [K(z) for z in (A,B,x1,y1,x2,y2,x3,y3)]

# 4) Build x((P+Q)+R) and x(P+(Q+R))
x12 = xAdd(x1,y1,x2,y2);  y12 = yAdd(x1,y1,x2,y2)
x23 = xAdd(x2,y2,x3,y3);  y23 = yAdd(x2,y2,x3,y3)

xA  = xAdd(x12,y12,x3,y3)   # x((P+Q)+R)
xB  = xAdd(x1,y1,x23,y23)   # x(P+(Q+R))

# 5) Take common-denominator numerator and reduce modulo the curve ideal
diff = xA - xB
num  = diff.numerator()  # element of R up to a unit; denominators assumed nonzero (generic position)

I = R.ideal([
    y1**2 - (x1**3 + A*x1 + B),
    y2**2 - (x2**3 + A*x2 + B),
    y3**2 - (x3**3 + A*x3 + B)
])

rem = I.reduce(num)       # Gröbner normal form modulo the curve ideal
print(rem.is_zero())

The program outputs True, indicating that the associativity of point addition on the elliptic curve holds.

9-Points Theorem

In fact, this conclusion holds not only on elliptic curves but also on general cubic curves:

(Theorem Two:) In the projective plane ${\mathbb{P}}_K^2$ (where $K$ is the field of definition), let $C$ be a cubic curve defined by the homogeneous cubic polynomial $C(x,y,z)=0$. Given three lines $l_1,l_2,l_3$ and another three lines $m_1,m_2,m_3$ such that $l_i\ne m_j$, their intersection points $P_{ij}=l_i\cap m_j$ (excluding $P_{33}$) are all non-singular points on $C$. If these eight points are distinct (the original theorem does not require this condition; for brevity, we do not discuss coincident points here), then the intersection point $P_{33}$ must also lie on the curve $C$.

An intuitive example is as follows, where $l_{1,2,3}$ are the red lines, $m_{1,2,3}$ are the blue lines, and the black curve is the cubic curve $C$:

(Proof Two:) The idea of the proof is to define $D=C-\alpha m_1{m}_2{m}_3-\beta l_1{l}_2{l}_3=0$, so that $C=\alpha m_1{m}_2{m}_3+\beta l_1{l}_2{l}_3$. Then, since $P_{33}$ lies on both $l_3$ and $m_3$, both $\alpha m_1{m}_2{m}_3$ and $\beta l_1{l}_2{l}_3$ vanish, leading to $C(P_{33})=0$, i.e., $P_{33}$ lies on the cubic curve $C$.

First, we parameterize the line equation $l(x,y,z)$. Suppose $l$ satisfies $ax+by+cz=0$ in ${\mathbb{P}}_K^2$. We can set:

$$\{\begin{array}{l}x=a_{1}u+b_{1}v\\ y=a_{2}u+b_{2}v\\ z=a_{3}u+b_{3}v\end{array}$$

to transform the line equation from $l(x,y,z)$ to $\tilde{l}(u,v)$. Since line $l_1$ passes through points $P_{11},P_{12},P_{13}$, let $(u_1,v_1),(u_2,v_2),(u_3,v_3)$ be the corresponding $(u,v)$ parameter pairs for these three points on $l_1$. Substituting the parameterization of $l_1$ into the equations of lines $m_j$ gives ${\tilde{m}}_j(u,v)$. Since $P_{11},P_{12},P_{13}$ lie on $m_1,m_2,m_3$ respectively, we have ${\tilde{m}}_j(u_j,v_j)=0$. On the other hand, points other than $P_{1j}$ do not lie on $m_j$, so ${\tilde{m}}_j(u,v)$ is a nonzero polynomial. Multiplying these three expressions, we obtain ${\tilde{m}}_1(u,v){\tilde{m}}_2(u,v){\tilde{m}}_3(u,v)$, a homogeneous cubic polynomial in $u$ and $v$.

Consider the following lemma:

(Lemma 2.1:) If two homogeneous cubic polynomials $R$ and $S$ intersect a line at three identical points (counting multiplicity), then there exists a constant $\alpha$ such that $R=\alpha S$.

The lemma is intuitively clear. From the perspective of univariate functions, if two cubic functions $R$ and $S$ share the same three roots (with the line $y=0$), say $x_1,x_2,x_3$ (which may coincide), then by the zero theorem, both functions must contain the polynomial $(x-x_1)(x-x_2)(x-x_3)$. Since this polynomial is already cubic, the only difference between $R$ and $S$ is a constant factor $\alpha$. The formal proof simply translates this univariate argument into projective and parameterized language, which we omit here.

For another homogeneous cubic polynomial $C$, apply the same $l_1$-parameterization to transform it into $\tilde{C}(u,v)$. Clearly, $\tilde{C}$ also passes through points $P_{11},P_{12},P_{13}$. By Lemma 2.1, there exists a constant $\alpha$ such that $\tilde{C}=\alpha {\tilde{m}}_1{\tilde{m}}_2{\tilde{m}}_3$.

Suppose the projective equation of $l_1$ is $ax+by+cz=0$, where $a,b,c$ are not all zero. Without loss of generality, assume $a\ne 0$, so:

$$\{\begin{array}{l}x=-(b/a)u-(c/a)v\\ y=u\\ z=v\end{array}$$

Let $C_1=C-\alpha m_1{m}_2{m}_3$. Then $C_1(l_1)=0$. Write $C_1$ as a polynomial in $x$: $C_1(x,y,z)=a_3(y,z)x^3+a_2(y,z)x^2+a_1(y,z)x+a_0(y,z)$. Note that:

$$x^n=(1/a{)}^n((ax+by+cz)-(by+cz){)}^n$$

Thus, we can rewrite:

$$C_1(x,y,z)=a_3^{\prime }(y,z)(ax+by+cz{)}^3+\cdots +a_0^{\prime }(y,z)=a_0^{\prime }(y,z)$$

and ${\tilde{C}}_1(u,v)=C_1(-(b/a)u-(c/a)v,u,v)=a_0^{\prime }(u,v)=0$ (since $C_1(l_1)\equiv 0$, independent of parameter choice). Since $a_0^{\prime }(u,v)=a_0^{\prime }(y,z)$, we have $(ax+by+cz)\mid (C(x,y,z)-\alpha m_1{m}_2{m}_3)$, i.e.:

$$l_1\mid (C-\alpha m_1{m}_2{m}_3)$$

Similarly, we have:

$$m_1\mid (C-\beta l_1{l}_2{l}_3)$$

Now define:

$$D=C-\alpha m_1{m}_2{m}_3-\beta l_1{l}_2{l}_3$$

It is easy to show that $m_1\mid D$ and $l_1\mid D$. Since $l_1$ and $m_1$ intersect but do not coincide, $gcd(m_1,l_1)=1$. By the unique factorization theorem, $m_1{l}_1\mid D$, i.e., $D=l_1{m}_{1}l$, where $l$ is also a linear form (a line).

Additionally, from the given conditions, $C(P_{22})=C(P_{23})=C(P_{32})=0$, and clearly $\alpha m_1{m}_2{m}_3+\beta l_1{l}_2{l}_3$ also vanishes at these points. Hence, $D(P_{22})=D(P_{23})=D(P_{32})=0$. Since $l_1$ and $m_1$ do not pass through these three points, we have $l(P_{22})=l(P_{23})=l(P_{32})=0$.

Note that two points determine a line. This implies that $l$ lies on both $l_2$ and $m_2$. Since $l_2\ne m_2$, the only possibility is $l\equiv 0$, which implies $D\equiv 0$. Therefore, we have $C=\alpha m_1{m}_2{m}_3+\beta l_1{l}_2{l}_3$, which is the conclusion we aimed to prove at the beginning. This shows that $P_{33}$ lies on $C$.

After proving the 9-points theorem, we can show that the addition on elliptic curves satisfies associativity. As shown in the figure below, let $P=P_{13}$, $Q=P_{11}$, $R=P_{31}$, and point $E$ is $-(P+Q+R)$, the intersection of $l_3$ and $m_3$. By the 9-points theorem, $C$, $l_3$, and $m_3$ are concurrent. Computing $-((P+Q)+R)$ gives the intersection of $l_3$ and $C$, while computing $-(P+(Q+R))$ gives the intersection of $m_3$ and $C$. Therefore, these two intersection points are the same. This verifies $-((P+Q)+R)=-(P+(Q+R))$, i.e., the associativity of point addition holds.

---

The 9-points theorem has a more general form:

(Theorem Three, Cayley–Bacharach:) Let $X,Y\subset {\mathbb{P}}^2$ be two cubic curves intersecting at nine distinct points $p_0,p_1,\cdots ,p_8$. If a cubic curve $Z\subset {\mathbb{P}}^2$ passes through $p_1,\cdots ,p_8$, then it also passes through $p_0$.

It is easy to see that if $X$ and $Y$ degenerate into unions of three lines, this theorem reduces to the 9-points theorem.

(Proof Three:) This is a classical result in algebraic geometry. You can find it in Hartshorne's GTM52 (page 400, Corollary 4.5). Also, see the link on Banana Space: Cayley–Bacharach Theorem.

Pascal/Pappus

(Corollary Four, Pascal:) Let $ABCDEF$ be a hexagon inscribed in a conic $\mathrm{\Gamma }$ (ellipse, parabola, or hyperbola), where $A,B,C,D,E,F$ are distinct points in the affine plane. Let $X$ be the intersection of $\overline{AB}$ and $\overline{DE}$, $Y$ be the intersection of $\overline{BC}$ and $\overline{EF}$, and $Z$ be the intersection of $\overline{CD}$ and $\overline{FA}$. Then the three points $X,Y,Z$ are collinear. As shown in the figure:

(Proof Four:) Let $l_1=\overline{EF}$, $l_2=\overline{AB}$, $l_3=\overline{CD}$, $m_1=\overline{BC}$, $m_2=\overline{DE}$, $m_3=\overline{FA}$. We can list the intersection table of the line family $l$ and the line family $m$:

	$l_1$	$l_2$	$l_3$
$m_1$	$Y$	$B$	$C$
$m_2$	$E$	$X$	$D$
$m_3$	$F$	$A$	$Z$

Let $Q(x,y,z)=0$ be the projective form of $\mathrm{\Gamma }$, and let $l(x,y,z)=0$ be the projective form of the line $\overline{XY}$. Then:

$$C(x,y,z)=Q(x,y,z)l(x,y,z)$$

is a homogeneous cubic polynomial, and $C=0$ must pass through the points $A,B,C,D,E,F,X,Y$. Since these eight points are all non-singular points in ${\mathbb{P}}^2$, the conditions of Theorem 2 (9-points theorem) are satisfied. By Theorem 2, we have $C(Z)=0$, and clearly $Q(Z)\ne 0$, so $l(Z)=0$. Therefore, $X,Y,Z$ are collinear.

---

(Corollary Five, Pappus:) Let $l$ and $m$ be two distinct lines in the plane, $A,B,C$ be distinct points on $l$, and $A^{\prime },B^{\prime },C^{\prime }$ be distinct points on $m$. Assume none of these points is the intersection of $l$ and $m$. Let $X$ be the intersection of $\overline{A{B}^{\prime }}$ and $\overline{A^{\prime }B}$, $Y$ be the intersection of $\overline{B^{\prime }C}$ and $\overline{B{C}^{\prime }}$, and $Z$ be the intersection of $\overline{C{A}^{\prime }}$ and $\overline{C^{\prime }A}$. Then the three points $X,Y,Z$ are collinear. As shown in the figure:

(Proof Five:) Here, $l$ and $m$ represent the degenerate case of the conic in Theorem 4, and the corresponding hexagon is $A{B}^{\prime }C{A}^{\prime }B{C}^{\prime }$.

Poles and Polar Lines

After learning about Pascal's theorem for ellipses, I recalled that some classmates in high school introduced properties related to poles and polar lines of conic sections. It seems these two concepts should be connected. First, let's define poles and polar lines (using an ellipse as an example):

（Definition Six, Pole and Polar Line:）

• If point $P$ lies inside the ellipse, draw two secants through $P$ intersecting the ellipse at points $A,B$ and $C,D$. If lines $AC$ and $BD$ intersect at point $S$, and lines $AD$ and $BC$ intersect at point $T$, then $P$ and line $ST$ form a pole and its polar line.
• If point $P$ lies outside the ellipse, draw two tangents from $P$ to the ellipse. The line connecting the two points of tangency is the polar line of the pole $P$.
• If point $P$ lies on the ellipse, the tangent to the ellipse at $P$ is its polar line.

One fundamental property of poles and polar lines is the principle of polarity, stated as follows:

（Corollary Seven, Principle of Polarity:） For the same ellipse, if the polar line of point $P$ passes through point $Q$, then the polar line of point $Q$ passes through point $P$.

（Proof Seven:） Here, we provide a purely geometric proof using only Pascal's theorem. First, consider the case where $P$ is inside the ellipse. According to the definition, construct its polar line $IJ$:

The original proof reduces to proving that the tangency points $D$ and $K$ of point $Q$ with the ellipse satisfy the condition that $D,P,K$ are collinear. Draw another secant $QL$ through $Q$ and temporarily hide other lines to obtain the following diagram:

We can see that $HELGFM$ forms a hexagon inscribed in the ellipse. According to Pascal's theorem, the three intersection points $X,Y,Z$ of $\overline{HE}$ and $\overline{GF}$, $\overline{EL}$ and $\overline{FM}$, and $\overline{LG}$ and $\overline{MH}$ are collinear (which indirectly proves that the polar line is a straight line):

Clearly, point $X$ here is the same as point $P$ mentioned earlier, so we can conclude that $P$ lies on line $YZ$. The choice of secant $QL$ is arbitrary. If we let points $L$ and $M$ approach each other infinitely (i.e., $QL$ becomes tangent to the ellipse), we find that $Y$ and $Z$ coincide with the tangency point $L$:

Therefore, we can conclude that line $PYZ$ passes through the tangency point $L$. Similarly, it also passes through the other tangency point $L^{\prime }$ of point $Q$ with the ellipse. According to the definition of the polar line of a point outside a circle, $L{L}^{\prime }$ is the polar line of $Q$. Since two points determine a line, $L{L}^{\prime }$ coincides with $PYZ$, so $P$ lies on the polar line of $Q$.

---

The case where $P$ lies on the ellipse is straightforward. First, the polar line of $P$ is the tangent to the ellipse at $P$. Conversely, take any other point $Q$ on this tangent. Draw the two tangents from $Q$ to the ellipse. One of the tangency points is $P$, so $P$ naturally lies on the polar line formed by connecting the two tangency points.

---

Now, consider the case where $P$ lies outside the ellipse. According to the definition, draw two tangents from $P$ to the ellipse. Connect the two tangency points $D$ and $E$ to obtain the polar line $DE$ of $P$. Then, take a point $Q$ on $DE$ and construct its polar line $JK$ according to the definition. This gives the following diagram (the original proposition reduces to proving that $J,P,K$ are collinear):

Consider the degenerate case of the hexagon $HHGFFI$ inscribed in the ellipse. The intersection points are $K$ (intersection of $HG$ and $FI$), $J$ (intersection of $GF$ and $IH$), and $X$ (not shown, intersection of the tangents to the ellipse at $H$ and $F$). According to Pascal's theorem, $J,X,K$ are collinear. Therefore, $X$ lies on the polar line $JK$ of point $Q$.

Now, rotate line $HF$ around point $Q$ until it coincides with $DE$. Since the polar line depends only on the position of point $Q$, this operation does not change the position of the polar line $JK$. By the definition of points $D$ and $E$, $X$ must coincide with point $P$. Therefore, we have proven that $P$ lies on $JK$, i.e., $J,P,K$ are collinear.

Reference Materials

Elliptic Curves: Number Theory and Cryptography

https://www.bananaspace.org/wiki/Cayley–Bacharach_定理

https://en.wikipedia.org/wiki/Cayley–Bacharach_theorem