title |
tags |
35. 挠群和除子 |
zk |
abstract algebra |
elliptic curve |
group theory |
finite field |
pairing |
torsion group |
divisor |
rational function |
|
在学习 Weil 配对之前,我们需要介绍它用到的数学工具:挠群和除子,前者提供了性质良好的点群,后者使得 Weil 配对能够在数学上精确地描述点之间的配对关系。
挠点(torsion points)指在椭圆曲线上具有有限阶的点。即存在正整数 $m \geq 1$,使得对于椭圆曲线 $E$ 上的点 $P$,有 $mP = O$,其中 $O$ 是曲线的单位元(无穷远点)。点 $P$ 的阶即为 $m$,此时 $P$ 被称为挠点。
我们可以将所有阶为 $m$ 的倍数的点集合起来,就构成了 $m$-挠群(torsion group),定义为:
$$
E[m] = \set{P \in E: mP = O}
$$
挠群 $E[m]$ 是椭圆曲线 $E$ 的一个加法子群,其中单位元是无穷远点 $O$。如果 $P, Q \in E[m]$,则 $P+Q$ 和 $-P$ 也属于 $E[m]$,说明挠群具有封闭性和存在逆元,因此构成一个群结构。
当椭圆曲线定义在域 $K$ 上时,$m$-挠群记为 $E(K)[m]$。例如,定义在 $\mathbb{F}_p$ 上的 $E$ 的 $m$-挠群写作 $E(\mathbb{F}_p)[m]$。
我们以椭圆曲线 $E(\mathbb{F}_{19})$,方程为 $y^2 = x^3 - x + 1$。椭圆曲线上共有 22 个元素,11-挠群中共有 11 个点,它们是:
- (0, 18)
- Infinity (无穷远点)
- (18, 18)
- (0, 1)
- (5, 11)
- (3, 14)
- (5, 8)
- (18, 1)
- (3, 5)
- (1, 1)
- (1, 18)
下面是椭圆曲线 $E(\mathbb{F}_{19})$ (红色+蓝色)和 $11$-挠群(红色)上的点的可视化:
挠群有个很重要的性质:
对于椭圆曲线 $E(\mathbb{F}_p)$,若 $m$ 与 $p$ 互质,那么存在正整数 $k$,使得
$$
E(\mathbb{F}_{p^{k}})[m] \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}
$$
成立。也就是说,存在扩域 $\mathbb{F}{p^{k}}$ 上椭圆曲线的挠群 $E(\mathbb{F}{p^{k}})[m]$ 同构于两个阶为 $m$ 的循环群的直积。这表明在某些扩域中,挠群可以视为一个2维向量空间,为 Weil 配对提供了一个有限的、结构良好的点群。
有理函数(Rational Function)是形式为 $A/B$ 的函数,其中 $A$ 和 $B$ 是多项式函数,且 $B$ 不恒等于零。有理函数可以定义为:
$$
f(x) = \frac{A(x)}{B(x)}
$$
其中, $A(x)$ 和 $B(x)$ 是多项式: $A(x) = \sum_{j=0}^{n}{a_jx^j}$ 和 $B(x) = \sum_{j=0}^{m}{b_jx^j}$。
如果我们分别对 $A(x)$ 和 $B(x)$ 进行质因式分解并考虑复数,有理函数可以写为另一种形式:
$$
f(x) = \frac{a(x - \alpha_1)^{e_1}...(x - \alpha_r)^{e_r}}{b(x - \beta_1)^{d_1}...(x - \beta_s)^{d_s}}
$$
下面是有理函数的性质:
- 加法性: 有理函数可以通过加法和乘法运算组合形成新的有理函数。
- 零点(zeros)和极点(poles): 有理函数的零点是使函数值为 0 的点,也就是所有使得分子 $P(x_0) = 0$ 的 $x_0$,也就是 $\set{\alpha_1, ..., \alpha_r}$;极点是函数值趋向无穷大的点,也就是所有使得分母 $Q(x_1) = 0$ 的点 $x_1$,也就是 $\set{\beta_1, ..., \beta_s}$。而 $\set{e_1, ..., e_r, d_1, ..., d_s}$ 是零点和极点的重数。
- 除子: 有理函数的零点和极点可以用来定义函数的除子。
举个例子,设多项式 $f(x) = \frac{x^3 - 2x}{2(x^2 - 5)}$,它的零点为 $\set{0, \sqrt{2}, - \sqrt{2}}$,极点为 $\set{\sqrt{5}, - \sqrt{5}}$。
除子(Divisor)是椭圆曲线上点的形式和,可以看作是一种“加权”点的概念,用于追踪有理函数上的零点和极点。如果在 $\alpha_1$ 处有 $e_1$ 个零点,就记为 $e_1 [\alpha_1]$;如果在 $\beta_1$ 处有 $d_1$ 个极点,就记为 $- d_1 [\beta_1]$,然后再把它们形式的加起来(不是普通的加法运算):
$$
\text{div}(f) = e_1 [\alpha_1] + ... + e_r [\alpha_r] - d_1 [\beta_1] - ... - d_s [\beta_s]
$$
举个例子,多项式 $f(x) = \frac{x^3 - 2x}{2(x^2 - 5)}$,它的零点为 $\set{0, \sqrt{2}, - \sqrt{2}}$,极点为 $\set{\sqrt{5}, - \sqrt{5}}$,这些零点和极点的重数都为 1。因此它的除子:
$$
\text{div}(f) = [0] + [\sqrt{2}] + [- \sqrt{2}] - [\sqrt{5}] - [- \sqrt{5}]
$$
椭圆曲线是满足以下方程的点的集合,加上一个无穷远点 $O$:
$$
y^2 = x^3 + ax + b
$$
其中 $a, b$ 是系数。我们可以把所有椭圆曲线上的点 $P(x,y)$ 的坐标用方程 $E(x,y) = y^2 - x^3 - ax - b = 0$ 表示。这样,我们就可以定义椭圆曲线上的二元有理函数:
$$
f(x,y) = \frac{A(x,y)}{B(x,y)}
$$
其中 $A(x,y), B(x,y)$ 是定义在椭圆曲线上的多项式,满足 $E(x,y) = 0$,且 $B(x,y)$ 不恒等于零。分子 $A(x,y)= 0$ 是 $f(x,y)$ 的零点,分母 $B(x,y)= 0$ 是 $f(x,y)$ 的极点,它们都定义在椭圆曲线上。
接下来我们可以定义椭圆曲线上有理函数的除子:
$$
D= \text{div}(f) = \sum_{P \in E}{n_P[P]}
$$
其中 $n_P \in \mathbb{Z}$ 是在点 $P$ 的零点或极点的重数。由于椭圆曲线上仅有有限个零点和极点,其余的点对应的重数 $n_P$ 均为零,因此 $D$ 中的求和是有限的。
椭圆曲线上的除子有两个很重要的概念:除子的度(degree)和除子的和(sum):
-
除子的度:定义为 $n_P$ 的和:
$$
\text{deg}(D) = \sum_{P \in E} n_P
$$
-
除子的和:定义为除子去掉中括号后的和:
$$
\text{sum}(D) = \sum_{P \in E} n_P P
$$
椭圆曲线 $E$ 上的除子有几个重要性质(证明超出本教程范畴,可以在专门的椭圆曲线教材中找到):
性质1. 除子的唯一性定理 如果定义在椭圆曲线 $E$ 上的两个非零的有理函数 $f$ 和 $g$ 的除子相同,即满足 $\text{div}(f) = \text{div}(g)$,那么这两个函数必定是相互成比例的,即存在一个常数 $c$ 使得 $f = cg$。
这个性质说明了有理函数的除子能够唯一确定该有理函数(乘以一个非零常数因子),对于双线性配对非常重要。
性质2. 主除子定理 一个除子 $D = \sum_{P \in E}{n_P[P]}$ 是椭圆曲线上的有理函数的除子,当且仅当它的度数为零 $\text{deg}(D) = 0$,且除子的和为椭圆曲线上的无穷远点 $\text{sum}(D) = O$。特别的,如果一个椭圆曲线上的有理函数没有零点或极点,那么它是一个常量。
首先,这个定理提供了一种判断给定除子 $D$ 是否对应于某个有理函数的方法;其次,对于双线性配对非常重要。
我们以椭圆曲线 $E: y^2 = x^3 - x$ 为例,定义 $E$ 上的有理函数 $f(x, y) = y$。我们可以观察 $f$ 在不同点上的行为来构造它的除子。由于 $x^3 - x = x(x+1)(x-1)= 0$ 的 3 个根为 $0, -1, 1$,因此 $f$ 有3个零点,分别在 $P_1(0,0), P_2(-1,0), P_3(1,0)$,他们的重数均为 $1$。并且 $f$ 在无穷远点 $O$ 有一个极点(因为在椭圆曲线上, $y$ 在无穷远处趋向于无穷大),根据主除子定理,无穷远点的极点的重数为 $3$。因此,咱们的除子可以写为:
$$
\text{div}(f) = [P_1] + [P_2] + [P_3] - 3 [O]
$$
其中除子的度 $\text{deg}(D) = 1 + 1 + 1 - 3 = 0$。由于 $P_1, P_2, P_3$ 三点共线,有 $P_1 + P_2 + P_3 = O$,因此,除子的和 $\text{sum}(D) = P_1 + P_2 + P_3 - 3 O = O - 3O = O$。
下面我们举个结合挠群和除子的例子。我们选一个定义在 $F_5$ 上的椭圆曲线 $E: y^2 = x^3 - x \pmod{5}$。
它有3个根,分别为 $0, -1, 1$,对应椭圆曲线上的3个点 $P_1(0,0), P_2(-1,0), P_3(1,0)$。由于他们满足 $2P_1 = 2P_2 = 2P_3 = O$,因此它们加上无穷远点 $O$ 构成了椭圆曲线的 $2$-挠群 $E[2] = \set{P_1, P_2, P_3, O}$。可以看到 $E[2]$ 包含4个点,同构于 $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$。
我们可以定义在 $E[2]$ 上的有理函数 $f(x, y) = \frac{x + 1}{x-1}$。这个函数在 $P_2$ 有一个零点,在 $P_3$ 有一个极点。因此,它的除子可以写为:
$$
D = \text{div}(f) = 2[P_2] - 2[P_3]
$$
注意, $m$-挠群的零点或极点的重数为 $m$。
这个除子的度为 $\text{deg}(D) = 2 - 2 = 0$,和为 $\text{sum}(D) = 2P_2 - 2P_3 = O - O = O$。
这一讲,我们介绍了 Weil 配对使用的两个数学工具:挠群和除子。 $m$-挠群包含椭圆曲线上阶为 $m$ 的点,为 Weil 配对提供了一个有限的、结构良好的点群;除子基于有理函数,是椭圆曲线上点的形式和,支持 Weil 配对在数学上精确地描述点之间的配对关系。下一讲,我们将介绍 Weil 配对。