椭圆曲线深入研究（第七部分）

走到这里一定不容易。

我们已经涵盖了广泛的概念，从简单的东西到一些非常抽象的想法。

嗯，如果你觉得到目前为止事情已经很复杂了…… 好吧，抓住你手边的任何东西。 事情将变得非常疯狂。

因为今天，我们将讨论 配对。 与我之前关于该主题的文章形成鲜明对比的是，这次我们将深入了解更精细和具体的细节。

因此，配对将在 连续两次交付 中解决：第一部分（本文）将侧重于建立一些基础，我们将在第二部分（下一篇文章）中定义配对。

这将是很长的一篇文章。 深吸一口气。 喝杯咖啡。 准备好了吗？ 让我们开始吧。

配对概览

首先，什么是配对？

通俗地说，配对 或 双线性映射 是一个函数，它接受两个输入，每个输入属于一个群，并输出另一个群的元素。 更正式地说，我们写成：

现在，这不仅仅是任何一种函数——要使其成为配对，它必须具有非常特殊的性质。 这种性质称为 双线性：这意味着它在两个输入中都是 线性的。

这是什么意思？ 假设群运算可以分别用 𝔾 ₁、𝔾 ₂ 和 𝔾 ₃ 的 +、· 和 * 表示。 双线性本质上意味着以下两个等式都成立：

我知道，这看起来并没有那么疯狂。 但是这个特性使得可以巧妙地四处移动东西。 例如，很容易看出：

我随意使用了指数表示法，因为我们总能找到与乘法的同构。 但请记住，指数表示重复应用群运算。

这些我们可以使用配对进行的小技巧可以实现各种很酷的密码学原语，例如 基于身份的加密 (IBE) 和对于一些现代零知识证明至关重要的工具。 当然，还有其他的。

而这就是简单部分的结束。

现在的问题是我们需要找到 合适的群，并定义一些 函数，使其表现得像双线性映射。 当然，我们可以推断出这些群与我们值得信赖的椭圆曲线有关。 但这不像仅仅选择两条随机曲线那么简单——我们需要更多才能使其工作。

特别是，我们需要再次回顾椭圆曲线群的群结构。

椭圆曲线子群

在前一篇文章中，我们探讨了椭圆曲线群的结构如何可以用 Mordell-Weil 定理来描述：

我们可以将其分为 无限阶 的子群（与整数同构）和 有限阶 的子群。

正如我们所知，有限域上的椭圆曲线群是有限的——在 p × p 网格上只能容纳这么多点。 因此，那些无限阶子群对我们来说并不是那么重要——将注意力集中在有限阶子群上更有意义。

通过按适当的系数缩放曲线，我们可以确保这些有限子群中的每个点不仅是合理的，而且是 整数值。 这就是我们获得有限域上的椭圆曲线群的方式。

我们关注的这些子群非常特殊，并且有自己的名称：它们被称为 挠群。

它们正是我们构建配对所需要的。

挠群

挠群是这样的子群，对于某个整数 r，其所有元素 P 都具有乘以 r 时得到 𝒪 的性质。 所以基本上，对于子群中的每个点，[r]P = 𝒪。 我们将其写为 E[r]——E 的 r-挠。

此外，如果 P 是 E[r] 的生成元，我们可以看到子群中的每个其他点也属于挠群，因为 [r]([n]P) = [n]([r]P) = [n] 𝒪 = 𝒪 .

因此，群 E[r] 也是映射 [r]: P → P 或乘以 r 的 核。 请记住，核只是 根 的广义概念。

现在我们回到有限域。 如前所述，很明显，整个椭圆曲线群是有限的。 然而，值得记住的是，正如我们在上一篇文章中探讨的那样，在椭圆曲线上找到整数值点是非常重要的。

同样很明显，由于我们可以使用的点数量有限，因此我们保证会有一些循环子群。 最多，整个群将是一些大小为 r 的单个循环。

接下来的是非常令人困惑的。 有一个定理，称为 有限阿贝尔群的结构定理（这是一个很长的名称），指出：

这意味着这两个群之间存在某种同构，这也意味着它们具有相同的大小（这是一一对应的关系）。

想想这会产生什么后果。 也就是说，r-挠应该具有 r² 的大小。 如果 r 大于 p（我们有限域的大小），我们甚至没有那么多可用的点！

因此，寻找这些剩余的点迫使我们查看 域扩展。

扩展曲线

使用域扩展对我们来说并不是一个新概念。 我们已经知道它是如何工作的：我们将一些元素附加到我们的有限域，导致它变得更大。 其中一个例子是 复数扩展：通过将 i 添加到域中——使得 i² + 1 = 0 ——，突然在扩展域中出现了无数个新的（复数）数字，并且它的大小增长到 p²。

同样，也有更多可用的点。 其中一些也满足椭圆曲线方程 E，因此椭圆曲线群的大小 也增加了。

复数在这里有点 显而易见的选择 ——但它们不是 唯一可用的选择。 事实上，我们可以实现任何大小为 pᵏ 的扩展，其中 k 是一个称为扩展 度 的整数。

我想在这里精确一点。 让我们再次使用 𝔽₁₇。 假设我们想通过添加一个元素 α 来扩展该域，使得 α³ - 2 = 0。 问题是这个方程在该域中有一个解：8！ 你可以自己检查一下。

因此，我们需要小心我们选择的元素是否有意义。 如果我们在 𝔽₇ 上尝试相同的扩展，你会发现 α³ - 2 = 0 在该域中没有解，因此这是一个有效的 3 次的扩展，总共有 7³ 个元素。

我们可以创建任何度的扩展——并且度本身由我们对附加到域中的新元素施加的多项式条件中的最高幂给出。

扩展和挠

考虑到这一点，我们可以回到这里的这个表达式：

我们问自己：我们需要找到所有缺失的 r-挠点的最小的 k 是多少？

这个最小的 k 在这种上下文中有一个特殊的名称：它被称为 嵌入度。 它是最小的正整数，使得 r 除以 pᵏ - 1，这是扩展域中群的大小。

这也写成 r | (pᵏ - 1)，意思是 “r 除以 (pᵏ — 1) ”。

乍一看，这个要求可能似乎不够——毕竟，我们它并不能保证 r-挠的所有 r² 个点都属于我们的域。 事实证明，尽管如此，这个条件 通常就足够了。 这与包含 单位的 r 次方根 的域有关，单位的 r 次方根是一些域元素 z，使得 zʳ mod p = 1。

我们真正需要的只是 r 是素数。

好吧，假设我们已经找到了一个合适的域扩展。 现在怎么办？

让我们看看。 我们知道 r-挠有 r² 个元素。 我们也知道 r-挠中的每个子群都有 r 个元素。 并且所有这些群都有一个共同的元素：𝒪 . 所以它们中的每一个都有 r - 1 个不同的元素。

这意味着总共有 r + 1 个 r-挠中的子群。 这是因为：

如果我们也计算 𝒪，我们得到的总数是 r² 个点！

最初是基域上的单个子群，经历某种演变，并转化为更多的群。

曲线 E/F₁₁ 的 3-挠：y² = x³ + 4。 𝒪 对所有子群都是通用的。

这些子群将是构建配对的关键。

在我们真正看到如何构建配对之前，我们仍然需要对这些群说几句话。 坚持住，伙计们。

迹映射

使这些挠子群有用的部分原因是它们之间存在一些具有非常特殊属性的 映射 或 函数。

作为值得注意的例子，我们已经讨论过曲线上的 扭曲。

另一个这样的函数是所谓的 迹映射，用 Tr 表示。 它的定义非常复杂。 这是它的样子：

我知道。 那是什么鬼东西。

让我们（逐个）分解它。

π 函数只是我们几篇文章前讨论过的弗罗贝尼乌斯自同态。 我们看到了它如何在基域的元素上起微不足道的作用——但对于域扩展，这是另一回事。 通常，应用自同态会产生另一个点。

但是 σ 到底是什么？ 同样，这是我们已经看到的东西：伽罗瓦群 的元素。

作为快速提醒，伽罗瓦群基本上是域自同构的集合。 自同构只是随意地排列元素，但保留了域结构。 在我们的扩展中，这些自同构有望使基域 (𝔽ₚ) 中的元素保持不变。

对于有限域，伽罗瓦群是 循环的（函数循环），由弗罗贝尼乌斯自同态 生成 — 每个元素 σ 只是 π 的某个幂，这就是我们在公式中看到的。

迹映射具有一个有趣的属性：它将域扩展中的元素映射到 基域 中——它有点像 投影 或 压缩。

通过显示 π(Tr(P)) = Tr(P)，很容易证明这一点。 我将它作为练习留给你！

它还有另一个更疯狂的属性：它是 线性的。 这意味着，对于任何点 P 和 Q，那么 Tr(P + Q) = Tr(P) + Tr(Q)。 乍一看这并不明显，但我们可以通过检查迹映射的每个组成部分（它是弗罗贝尼乌斯自同态的幂）来了解为什么会这样。

本质上，为了使这项工作正常进行，以下等式应该成立：

而且神奇的是，在有限域中，这有效。 扩展公式为：

所有系数都恰好可以被 p 整除，除了 aᵖ 和 bᵖ 的系数——这意味着所述系数与 0 模 p 同余，因此它们消失了！

这被称为 “ 新生的梦想”。 他们没有告诉你的事情是，它适用于有限域！

因此，弗罗贝尼乌斯自同态是线性的，它的幂也是线性的，迹也是线性的。

迹映射的线性也保证了一件事。 当应用于 r-挠时，我们已经知道我们将在基域上获得一个群。 但结果也将属于 r-挠中的一个子群。 因为线性会导致这种情况：

如果 P 是 r-挠中的一个点，那么 [r]P = 𝒪。 因此 [r]Tr(P) 将等于 Tr( 𝒪) _，根据定义，它是 𝒪。

挠结构

为了结束这一切，我想谈谈 r-挠中的一些特殊子群。 同样，所有这些对于配对构造都很重要。

在基域上，我们（通常）在 r-挠中得到一个子群。 这通常被称为 基域子群，我们用 𝒢 ₁ 表示。 当我们将迹映射应用于挠子群时，这正是我们获得的群，因此我们可以说：

现在，我将向你展示一种奇怪的复杂方式来编写 𝒢 ₁。 它可以写成：

Ker 只是意味着 核。 我们过去已经充分讨论过这个问题，但它只是当我们应用手头的自同态（函数 π - [1]）时我们得到 𝒪 的那组点。 我们知道 π 在基域上起微不足道的作用——因此该核正是 𝔽ₚ。

𝒢₁ 是 r-挠中属于基域的那组点。

我们说 𝒢 ₁ 是限制为 E[r] 的 π 的 [1]-本征空间。 本征空间 当然是指 本征值 的概念，在椭圆曲线的上下文中，本征值是与满足以下条件的那组点 P 相关联的值 λ：

因此，1 是弗罗贝尼乌斯自同态的本征值。 但它不是 唯一 的本征值。

特征多项式

第二个本征值不太明显，为了找到它，我们需要了解弗罗贝尼乌斯自同态的 特征多项式。

长话短说，特征多项式是这个函数：

解释这来自哪里可能需要另一篇完整的文章——所以再次，我请你做一件小小的信任行为。

该方程中的 t 是一个有趣的值：它是 弗罗贝尼乌斯的迹。 本质上，如果我们的椭圆曲线群的大小为 #E，那么 t = #E - p + 1。

为了找到 π 的本征值，我们假设 π(P) = [ λ ]P，并代入上述方程，得到：

为了使此等式成立，我们要求括号之间的值为 0。 这会产生两个结果——让我们称它们为 α 和 β。 它们是本征值，并且使用一些基本的代数知识，我们知道它们必须满足两个条件：

• α + β = t
• αβ = p

第二个条件尤为重要——我们已经知道一个本征值为 1。 因此，另一个本征值必须是 p！

使用第二个本征值（及其相关的本征空间），我们现在可以回收之前那个奇怪的定义，但使用这个新发现的结果：

换句话说，𝒢 ₂ 由 r-挠中的点 P 组成，使得 π(P) = [p]P。

这些群（𝒢 ₁ 和 𝒢 ₂）非常特别。 让我们花点时间谈谈它们。

正如我们已经提到的，𝒢 ₁ 被称为基域子群，这很有意义，因为我们已经知道它完全位于基域上。 相比之下，𝒢 ₂ 完全 存在于域扩展中。

这很有意义，因为 𝒢₂ 中的任何点 P 都应满足 π(P) = [p]P，如果 P 属于基域，那么我们将有 P = [p]P。 对于 r-挠中的点来说，这并不成立，除非 r 能整除 p。 由于 r 和 p 通常都是素数，因此我们得出结论，𝒢₂ 必须不存在于基域上。

两者都是阶数为 r 的循环子群，因为它们属于 r-挠。 它们的交集正是点 𝒪。 并且一起，它们具有一个显着的属性：它们 生成整个 r-挠。

有很多线索表明这一点。 例如，E[r] 同构于 ℤᵣ × ℤᵣ——ℤᵣ 上的 “维度 2” 空间。 此外，特征多项式也具有 2 次。 这些线索表明，r-挠的两个本征空间足以完全生成它——这仅仅意味着 E[r] 中的任何点 P 都可以唯一地分解为 P = P₁ + P₂，其中 P₁ ∈ 𝒢 ₁ ， 和 P₂ ∈ 𝒢₂。

哦，我们必须用一个名字来命名 𝒢 ₂。 我们称它为 迹零子群，因为 𝒢 ₂ 中的所有点 P 都具有 Tr(P) = 𝒪。 我们不会在这里展示为什么会这样，但同样，请随时自己尝试一下！

总结一下，我们知道 迹映射 将 E[r] 中的点映射到 𝒢 ₁. 那么 𝒢 ₂ 呢？ 有没有哪个映射可以做同样的事情？ 事实上，有一个，它被称为 反迹映射，定义为：

我们当然需要证明 Tr(aTr) = 𝒪。 我朋友，我把这项工作留给你。

总结

如果你已经做到了这一点，你肯定感觉自己好像被一辆装满数学怪异事物的卡车撞了。

Wheeee~

我知道这很激烈。 我知道有时候，这并不有趣。 我已经尽力保持它的清晰和某种程度上的娱乐性——但这种级别的数学无论你如何剖析它都具有挑战性，而且无论你如何看待它，都有越来越多的理论需要深入研究。

尽管如此，我们今天肯定已经覆盖了很多领域。

让我们回顾一下：我们介绍了 配对 或 双线性映射 的概念。 我们提到构建这样的函数并不容易，以及我们将需要一些特殊的群作为输入。

然后我们继续介绍这些群，探索域扩展中的 r-挠，并介绍 基域子群 (𝒢 ₁) 和 迹零子群 (𝒢 ₂) 作为 r-挠的生成元。 我们看到了 迹映射 和 反迹映射 如何允许我们将 r-挠中的元素压缩成 𝒢 ₁ 或 𝒢 ₂。

从一个好奇的人的角度来看，我会说，我发现我们今天所见的东西非常惊人和美丽。

当然，我们错过了锦上添花的一笔：这些东西在配对的构建中有什么作用。

那将是下一篇文章的主题。 到时见！

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～