为什么椭圆曲线点加满足结合律

这篇文章介绍椭圆曲线点加结合律的证明，以及更强的 9-points theorem。另外，也会涉及到该定理的三种推论：pascal 定理、pappus 定理，以及圆锥曲线极点极线的配极原则。

初等证明

（定理一：） 对于一个非奇异的椭圆曲线 $E : y^{2} = x^{3} + A x + B$ ，我们取相异的三点 $P, Q, R$ ，满足任意两点或者三点之和不为无穷远点 $O$ 。我们定义 $P + Q$ 为连接 $P, Q$ 的直线与 $E$ 的第三个交点，关于 $x$ 轴的对称点（显然该点也在 $E$ 上），则我们有：

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

（证明一：） 我们尝试用相对初等的方法来证明。设 $E$ 上的三点 $P, Q, R$ 的坐标为 $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3})$ 。则令 $λ_{a b} = \frac{y_{b} - y_{a}}{x_{b} - x_{a}}$ ：

P + Q = (λ_{12}^{2} - x_{1} - x_{2}, - λ_{12} ((λ_{12}^{2} - x_{1} - x_{2}) - x_{1}) - y_{1})

记该点为 $S (x_{s}, y_{s})$ ；

Q + R = (λ_{23}^{2} - x_{2} - x_{3}, - λ_{23} ((λ_{23}^{2} - x_{2} - x_{3}) - x_{2}) - y_{2})

记该点为 $T (x_{t}, y_{t})$ 。

然后计算：

x_{(P + Q) + R} = λ_{s 3}^{2} - x_{s} - x_{3}

x_{P + (Q + R)} = λ_{1 t}^{2} - x_{1} - x_{t}

然后验证 $x_{(P + Q) + R} = x_{P + (Q + R)}$ ，由于手工计算比较繁杂，这里使用 sagemath 的 Groebner 规约，验证差值为 $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())

程序输出 True，代表椭圆曲线上的点加结合律成立。

9-points theorem

事实上，这个结论不仅在椭圆曲线上成立，对于一般的三次曲线，也有这样的结论：

（定理二：） 在二次投影平面 $P_{K}^{2}$ （ $K$ 是平面的定义域）中，由齐次三次多项式 $C (x, y, z) = 0$ 定义的三次曲线 $C$ ，给定三条直线 $l_{1}, l_{2}, l_{3}$ 和另外三条直线 $m_{1}, m_{2}, m_{3}$ ，满足 $l_{i} \neq m_{j}$ ，它们的交点 $P_{i j} = l_{i} \cap m_{j}$ （除了 $P_{33}$ ）均为 $C$ 上的非奇异点。假如这八个交点互不相同（原定理无此条件，篇幅所限，不讨论点的重合情况），则交点 $P_{33}$ 必然也在曲线 $C$ 上。

一个直观的例子如下，这里的 $l_{1, 2, 3}$ 为红线， $m_{1, 2, 3}$ 为蓝线，而黑线即为三次曲线 $C$ ：

（证明二：） 证明的思路大致是令 $D = C - α m_{1} m_{2} m_{3} - β l_{1} l_{2} l_{3} = 0$ ，从而 $C = α m_{1} m_{2} m_{3} + β l_{1} l_{2} l_{3}$ ，这样的话 $P_{33}$ 因为同时在 $l_{3}$ 和 $m_{3}$ 上， $α m_{1} m_{2} m_{3}$ 与 $β l_{1} l_{2} l_{3}$ 就均为 $0$ ，从而得到 $C (P_{33}) = 0$ ，即 $P_{33}$ 在椭圆曲线 $C$ 上。

首先，我们尝试将直线方程 $l (x, y, z)$ 参数化，假如 $l$ 在 $P_{K}^{2}$ 满足方程 $a x + b y + c z = 0$ ，我们可以令：

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

将直线的方程从 $l (x, y, z)$ 化为 $\tilde{l} (u, v)$ 。由于直线 $l_{1}$ 过点 $P_{11}, P_{12}, P_{13}$ ，令 $(u_{1}, v_{1}), (u_{2}, v_{2}), (u_{3}, v_{3})$ 为直线 $l_{1}$ 在这三点分别对应的 $(u, v)$ 参数对。将 $l_{1}$ 的参数化等式代入直线 $m_{j}$ 得到 ${\tilde{m}}_{j} (u, v)$ ，由于 $P_{11}, P_{12}, P_{13}$ 分别在直线 $m_{1}, m_{2}, m_{3}$ 上，故有 ${\tilde{m}}_{j} (u_{j}, v_{j}) = 0$ 。另一方面，除 $P_{1 j}$ 之外的点都不在直线 $m_{j}$ 上，故 ${\tilde{m}}_{j} (u, v)$ 为非零多项式。将这三个式子相乘，可得 ${\tilde{m}}_{1} (u, v) {\tilde{m}}_{2} (u, v) {\tilde{m}}_{3} (u, v)$ 为关于 $u, v$ 的三次齐次多项式。

考虑以下引理：

（引理2.1：） 对于齐次三次多项式 $R, S$ 交一条直线于三个相同的点（记重数），则存在常数 $α$ 使得 $R = α S$ 。

引理的理解非常直观，从单变量函数的角度来看，例如如果两个三次函数 $R$ 和 $S$ 的三个根（直线 $y = 0$ ）完全相同，分别记为 $x_{1}, x_{2}, x_{3}$ （可以相同），由零点定理，这两个三次函数一定包含多项式 $(x - x_{1}) (x - x_{2}) (x - x_{3})$ ，而由于该多项式已经是三次函数，所以区分 $R$ 与 $S$ 的只能是常数项 $α$ 。具体的证明只需把单变量函数的语言换成射影、参数化的语言即可，这里略去。

对于另一个三次齐次多项式 $C$ ，对其使用同样的 $l_{1}$ -参数将其化为 $\tilde{C} (u, v)$ ，显然 $\tilde{C}$ 也过点 $P_{11}, P_{12}, P_{13}$ 。根据引理 2.1，存在一个常数 $α$ ，使得 $\tilde{C} = α {\tilde{m}}_{1} {\tilde{m}}_{2} {\tilde{m}}_{3}$ 。

设 $l_{1}$ 的投影方程为 $a x + b y + c z = 0$ ，其中 $a, b, c$ 不全为零。不失一般性，我们令 $a \neq 0$ ，故:

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

令 $C_{1} = C - α m_{1} m_{2} m_{3}$ ，有 $C_{1} (l_{1}) = 0$ 。将 $C_{1}$ 写为关于 $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)$ 。注意到：

x^{n} = (1 / a)^{n} ((a x + b y + c z) - (b y + c z))^{n}

因此可以变形为：

C_{1} (x, y, z) = a_{3}^{'} (y, z) (a x + b y + c z)^{3} + \dots + a_{0}^{'} (y, z) = a_{0}^{'} (y, z)

而 ${\tilde{C}}_{1} (u, v) = C_{1} (- (b / a) u - (c / a) v, u, v) = a_{0}^{'} (u, v) = 0$ （因为 $C_{1} (l_{1}) \equiv 0$ ，值与参数如何选取无关），而 $a_{0}^{'} (u, v) = a_{0}^{'} (y, z)$ ，故 $(a x + b y + c z) | (C (x, y, z) - α m_{1} m_{2} m_{3})$ ，即：

l_{1} | (C - α m_{1} m_{2} m_{3})

同理我们有：

m_{1} | (C - β l_{1} l_{2} l_{3})

现在我们令：

D = C - α m_{1} m_{2} m_{3} - β l_{1} l_{2} l_{3}

易证 $m_{1} | D, l_{1} | D$ 。而由于 $l_{1}, m_{1}$ 相交但不重合， $gcd (m_{1}, l_{1}) = 1$ 。因此由唯一分解定理， $m_{1} l_{1} | D$ ，即 $D = l_{1} m_{1} l$ ，其中 $l$ 也是一个一次式（直线）。

另外，我们由题设条件， $C (P_{22}) = C (P_{23}) = C (P_{32}) = 0$ ，显然 $α m_{1} m_{2} m_{3} + β l_{1} l_{2} l_{3}$ 在这几个点也为 $0$ ，故可以推出 $D (P_{22}) = D (P_{23}) = D (P_{32}) = 0$ ，而 $l_{1}$ 与 $m_{1}$ 不过这三个点，因此 $l (P_{22}) = l (P_{23}) = l (P_{32}) = 0$ 。

注意到两点确定一条直线，这意味着 $l$ 同时在 $l_{2}$ 和 $m_{2}$ 上，而 $l_{2} \neq m_{2}$ ，故唯一满足条件的 $l \equiv 0$ ，即可推出 $D \equiv 0$ 。于是我们有 $C = α m_{1} m_{2} m_{3} + β l_{1} l_{2} l_{3}$ ，也就是开头我们想要证到的结论，这样我们便说明了 $P_{33}$ 在 $C$ 上。

证明完 9-points theorem 后，我们便可以说明椭圆曲线的加法满足结合律。如下图所示，我们令点 $P = P_{13}, Q = P_{11}, R = P_{31}$ ，这里的点 $E$ 即为 $- (P + Q + R)$ ，是 $l_{3}, m_{3}$ 的交点。由 9-points theorem，可得 $C, l_{3}, m_{3}$ 三线共点。而按照 $- ((P + Q) + R)$ 的顺序计算出来的是 $l_{3}, C$ 的交点，而按照 $- (P + (Q + R))$ 的顺序计算出来的是 $m_{3}, C$ 的交点，因此这两个交点是同一个。我们便验证了 $- ((P + Q) + R) = - (P + (Q + R))$ ，也就是点加运算的结合律成立。

9-points theorem 还有一个更一般的情况，具体如下：

（定理三， Cayley–Bacharach：） 设 $X, Y \subset P^{2}$ 是两条三次曲线, 交于互异九点 $p_{0}, p_{1}, \dots, p_{8}$ .如三次曲线 $Z \subset P^{2}$ 过点 $p_{1}, \dots, p_{8}$ , 则它也过 $p_{0}$ .

容易看到， $X, Y$ 这两条三次曲线如果退化到三条直线的并集，那么该定理即为 9-points theorem。

（证明三：） 这是一个代数几何的经典结论，你可以在 Hartshorne 的 GTM52 中（第 400 页，推论 4.5）看到。另外也可见香蕉空间的链接。

Pascal/Pappus

（推论四， Pascal：） 设 $A B C D E F$ 是一个内接于圆锥曲线 $Γ$ （椭圆、抛物线或双曲线）的六边形，其中 $A, B, C, D, E, F$ 是仿射平面中的不同点。设 $X$ 为 $\overset{―}{A B}$ 与 $\overset{―}{D E}$ 的交点， $Y$ 为 $\overset{―}{B C}$ 与 $\overset{―}{E F}$ 的交点， $Z$ 为 $\overset{―}{C D}$ 与 $\overset{―}{F A}$ 的交点，则 $X, Y, Z$ 三点共线。如图所示：

（证明四：） 令 $l_{1} = \overset{―}{E F}, l_{2} = \overset{―}{A B}, l_{3} = \overset{―}{C D}, m_{1} = \overset{―}{B C}, m_{2} = \overset{―}{D E}, m_{3} = \overset{―}{F A}$ ，我们可以列出直线族 $l$ 与直线族 $m$ 的交点表：

	$l_{1}$	$l_{2}$	$l_{3}$
$m_{1}$	$Y$	$B$	$C$
$m_{2}$	$E$	$X$	$D$
$m_{3}$	$F$	$A$	$Z$

我们令 $Q (x, y, z) = 0$ 为 $Γ$ 的投影形式，再令 $l (x, y, z) = 0$ 为直线 $\overset{―}{X Y}$ 的投影形式，故：

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

为一个齐次三次多项式，而 $C = 0$ 一定过点 $A, B, C, D, E, F, X, Y$ 。由于这八个点均为 $P^{2}$ 上的非奇异点，因此定理二（9-points theorem）的适用条件成立。由定理二，可得 $C (Z) = 0$ ，而显然 $Q (Z) \neq 0$ ，故 $l (Z) = 0$ ，因此 $X, Y, Z$ 共线。

（推论五， Puppus：） 设 $l$ 和 $m$ 是平面中的两条不同直线， $A, B, C$ 是 $l$ 上的不同点， $A^{'}, B^{'}, C^{'}$ 是 $m$ 上的不同点，假设这些点中没有一个是 $l$ 和 $m$ 的交点。设 $X$ 为 $\overset{―}{A B^{'}}$ 和 $\overset{―}{A^{'} B}$ 的交点， $Y$ 为 $\overset{―}{B^{'} C}$ 和 $\overset{―}{B C^{'}}$ 的交点， $Z$ 为 $\overset{―}{C A^{'}}$ 和 $\overset{―}{C^{'} A}$ 的交点，则 $X, Y, Z$ 三点共线。如图所示：

（证明五：） 这里 $l, m$ 即定理四中圆锥曲线的退化情形，对应的六边形为 $A B^{'} C A^{'} B C^{'}$ 。

极点与极线

当知道在椭圆上的 pascal 定理后，回想起高中有同学科普圆锥曲线的极点极线相关的性质，觉得这两个应该可以关联起来。这里首先引出极点极线的定义（这里以椭圆为例）：

（定义六，极点极线：）

若点 $P$ 在椭圆内，过 $P$ 作两条割线交椭圆于 $A, B$ 和 $C, D$ 。若直线 $A C$ 与 $B D$ 交于点 $S$ ， $A D$ 与 $B C$ 交于点 $T$ 。则 $P$ 与直线 $S T$ 为极点和极线。
若点 $P$ 在椭圆外，则过 $P$ 作椭圆的两条切线，对应的切点连线即为极点 $P$ 的极线。
若点 $P$ 在椭圆上，则过 $P$ 作椭圆的切线即对应的极线。

而极点与极线一个最基本的性质就是配极原则，其叙述如下：

（推论七，配极原则：） 对于同一椭圆，如果点 $P$ 的极线经过点 $Q$ ，那么点 $Q$ 的极线经过点 $P$ 。

（证明七：） 这里提供一个仅使用 pascal 定理的纯几何证法。先考虑 $P$ 在椭圆内的情况，我们按照椭圆内一极点 $P$ ，按照定义做出其极线 $I J$ ：

原证明便转化为：要证点 $Q$ 与椭圆的切点 $D, K$ 满足 $D, P, K$ 三点共线。我们沿 $Q$ 再作一条椭圆的割线 $Q L$ ，并暂时隐去其他直线，便得到下图：

我们可以看到， $H E L G F M$ 构成椭圆内接六边形。按照 pascal 定理， $\overset{―}{H E}, \overset{―}{G F}$ 、 $\overset{―}{E L}, \overset{―}{F M}$ 、 $\overset{―}{L G}, \overset{―}{M H}$ 的三个交点 $X, Y, Z$ 共线（这也间接说明了极线是一条直线）：

显然，这里的点 $X$ 就是前面的点 $P$ ，所以我们可以说明 $P$ 在直线 $Y Z$ 上。而割线 $Q L$ 的选取是任意的，如果让点 $L, M$ 无限接近（即 $Q L$ 与椭圆相切），我们可以得到 $Y, Z$ 与切点 $L$ 重合：

因此我们可以得到结论，直线 $P Y Z$ 过切点 $L$ ；同理，它也过点 $Q$ 与椭圆的另一个切点 $L^{'}$ 。根据圆外一点对应极线的定义， $L L^{'}$ 即为 $Q$ 对应的极线。而根据两点确定一条直线， $L L^{'}$ 与 $P Y Z$ 重合，所以 $P$ 在 $Q$ 对应的极线上。

$P$ 在椭圆上的情况很简单，首先 $P$ 的极线就是过 $P$ 的切线。反过来的话，在切线上任取一个不同点 $Q$ ，沿点 $Q$ 作椭圆的两条切线，其中一个切点就是 $P$ ，这样 $P$ 自然也在两切点连线形成的极线上。

现在我们考虑 $P$ 在椭圆外的情况，首先根据定义，我们过 $P$ 作椭圆的两条切线。连接两个切点 $D, E$ ，即得到 $P$ 对应的极线 $D E$ 。之后我们在 $D E$ 上取一点 $Q$ ，按照定义作 $Q$ 对应的极线 $J K$ ，即可得到下图（原命题转化为证 $J, P, K$ 三点共线）：

考虑椭圆内接六边形的退化情形 $H H G F F I$ ，其交点分别为 $H G$ 与 $F I$ 的交点 $K$ ， $G F$ 与 $I H$ 的交点 $J$ ，以及 $H$ ， $F$ 各自与椭圆的切线形成的交点 $X$ （未画出）。根据 pascal 定理， $J, X, K$ 共线。故 $X$ 在点 $Q$ 对应的极线 $J K$ 上。

现在我们考虑将直线 $H F$ 绕点 $Q$ 旋转到 $D E$ ，由于极线仅仅与点 $Q$ 的位置有关，因此该操作不改变极线 $J K$ 的位置。而由点 $D E$ 的定义可知道 $X$ 一定与点 $P$ 重合，因此我们便证得 $P$ 在 $J K$ 上，即 $J, P, K$ 三点共线。

参考资料

Elliptic Curves: Number Theory and Cryptography

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

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