攀登高塔：域扩张

引言

有限域是每个密码学和 zk-SNARKs 的核心组成部分。实践中最常见的有限域是具有素数阶的 FpFp 域。定义它们的方法有很多种。一种常见的方法是将 FpFp 视为集合

{0,1,⋯,p−1}{0,1,⋯,p−1}

以及模 pp 的加法和乘法规则。但是其他有限域也扮演着重要的角色。例如，在处理 pairing-friendly 椭圆曲线时。你可能已经看到它们被表示为 FpnFpn。

定义和引入它们的常用方法是通过涉及 多项式环 的商的域扩张理论。从数学的角度来看，这是最自然和正确的方法，主要是为了证明关于它们的事情。但是，如果你不熟悉所涉及的数学工具，那么走这条路可能会显得晦涩难懂且令人困惑。

这个想法很简单，而且这些域是非常具体的数学对象。本文旨在提供一种非常规但更贴近实际的方式来理解有限域的扩展。

如果你想查看 zk-SNARKs 中有限域扩展的示例，你可以查看 arkworks 有限域算术库，他们在其中构建域扩展以处理椭圆曲线配对。

什么是域？

为了开始讨论，让我们重新审视一下什么是域。实际的定义在这里。

粗略地说，域是一个集合 FF，其加法和乘法规则的行为类似于实数。必须有一个元素 x0∈Fx0∈F 的行为类似于 00。这意味着对于 FF 中的所有 xx，x0+x=xx0+x=x。我们甚至将此元素仅表示为 00。类似地，必须有一个元素 11 在 FF 中，使得对于 FF 中的所有 xx，1⋅x=x1⋅x=x。它们分别被称为乘法和加法的 中性元素。在 FpFp 中，这些已经被表示为 00 和 11，所以没有什么好奇怪的。

一个域还必须对所有不同于 00 的元素具有 乘法逆元。这意味着如果 xx 是 FF 中任何不同于 00 的元素，则必须有另一个元素 yy 使得 x⋅y=1x⋅y=1。这个元素 yy 是唯一的，并且被表示为 x−1x−1。例如，在 F3F3 中，我们有 2−1=22−1=2。

我们可以从域的定义属性中推导出很多东西。稍后我们将需要这个：如果 x⋅x=0x⋅x=0，则 x=0x=0。

复数的情况

计算机科学家非常擅长命名事物，比如 神经网络 和 人工智能。另一方面，数学家在这方面往往很糟糕。在我们的早期生活中，我们遇到了最糟糕的例子之一：复数。它们至少存在三个问题。首先是名称。它使每个人都认为这是一个复杂的概念。其次，晦涩的表示法 a+bia+bi，最后，新符号被称为 虚数。这构成了一种爆炸性的组合，并掩盖了它的简单性。复数只是实数对，也称为 笛卡尔平面。有趣的是，有一种方法可以定义这组数对上的加法和乘法规则，以扩展实数的规则。这些甚至有几何解释！

我们引入这个是因为我们将采用类似于有限域的方法。该方法是：我们从一个域开始，在本例中是 RR，具有通常的加法和乘法规则。然后，我们添加一个新的坐标以获得实数对 (a,b)(a,b)。这个集合通常表示为 R2R2。在这个集合上，我们按分量定义加法 (a,b)+(c,d):=(a+c,b+d)(a,b)+(c,d):=(a+c,b+d)。然后我们尝试在上面定义一个乘法规则。也就是说，我们想要提出一个表达式 (a,b)⋅(c,d)(a,b)⋅(c,d) 的规则，使得：

1. 它与分量加法一起构成一个域。
2. 它通过以下方式扩展了实数运算。对于所有实数 aa 和 b,b，等式 (a,0)⋅(b,0)=(ab,0)(a,0)⋅(b,0)=(ab,0) 应该成立。这意味着我们可以认为实数位于 R2R2 内部。它们是那些具有空第二坐标的元素。并且在这个受限集合上，新运算可以归结为通常的运算。

如果我们尝试按分量定义乘法，我们将需要其他东西。也就是说，如果我们定义 (a,b)⋅(c,d)=(ac,bd)(a,b)⋅(c,d)=(ac,bd)，那么整个事情就不会是一个域。例如，不会有乘法的中性元素（想想看！）。虽然不明显，但事实证明有效的公式如下：

(a,b)⋅(c,d):=(ac−bd,ad+bc).(a,b)⋅(c,d):=(ac−bd,ad+bc).

这里乘法的中性元素是 (1,0)(1,0)。实数对的集合 R2R2 连同此乘法和分量加法是复数 CC 域。

标记 a+bia+bi

让我们来玩一下，以达到更熟悉的形式 a+bia+bi。 这也将是理解多项式环中的有限域的通常构造的关键。

由于我们可以将 R2R2 中的实数识别为具有空第二坐标的元素，因此我们可以滥用符号并写 aa 而不是 (a,0)(a,0)。 如果我们尝试对第二个坐标执行相同的操作，我们需要一种方法来区分它们与之前的坐标。 因此，我们将形式为 (0,b)(0,b) 的元素写为 bibi。 ii 表示它不是实数。 现在，点 (a,b)(a,b) 等于 (a,0)+(0,b)(a,0)+(0,b)。 使用新符号，它被写为 a+bia+bi。 请注意，符号 bibi 与我们对 RR 在 R2R2 内部的识别和乘法规则一致。 我们的意思是，当我们认为 bb 是 (b,0)(b,0) 并且 ii 是元素 (0,1)(0,1) 时，bibi 等于 b⋅ib⋅i。 也就是说，(b,0)⋅(0,1)=(0,b)(b,0)⋅(0,1)=(0,b)。

最后但并非最不重要的一点是，请注意 (0,1)⋅(0,1)=(−1,0)(0,1)⋅(0,1)=(−1,0)。 因此，在此符号下，这是 i2=−1i2=−1。

那么为什么我们更喜欢 a+bia+bi 符号而不是 (a,b)(a,b) 符号呢？ 我可以想到几个原因。 更明确的是，我们希望将实数视为位于复数内部。 它也更方便，因为它不涉及所有括号。 但这只是一个符号。

关键是复数是通过从实数添加更多坐标而构造的域。 相同的过程创建了所有有限域。 不同之处在于我们从域 FpFp 而不是 RR 开始。

等等，那实数的其他扩展呢？

既然我们已经像之前一样构造了复数 C:=R2C:=R2，我们可以尝试执行相同的过程并在复数对 C2C2 上定义乘法，使得与分量加法一起再次成为一个域。

我们可以做的另一件事是从实数开始，但这次添加三个或更多副本。 也就是说，尝试在实数的三元组 (a,b,c)(a,b,c) 上定义乘法以形成一个域。

这两者都需要更改。 这被称为 Frobenius 定理。 它指出我们能做的最好的事情是在 C2C2 上定义一个非交换乘法，这样它就不会是一个域。 它被称为 四元数。 这是一个迷人的对象，有很多应用，例如，在计算机图形学中，用于处理旋转。

好消息是，这两种结构都将在有限域的领域中发挥作用！

长度为 22 的二进制字符串

让我们从简单开始。 考虑 F2F2。 它只有两个元素

F2={0,1}F2={0,1}

加法和乘法规则分别为加法的中性元素为 00，乘法的中性元素为 11，1+11+1 等于 00。 加法是位集上通常的 XOR。 这将是我们的构建块。 域 F2F2 将在前一节中扮演实数的角色。

现在让我们添加一个坐标并考虑长度为 22 的所有二进制字符串的集合。 所以我们现在的集合是 (0,0),(0,1),(1,0),(1,1)(0,0),(0,1),(1,0),(1,1)。 我们现在将此集合称为 F22F22。 我们想在 F22F22 上找到一个乘法规则，就像在复数的情况下一样。 加法是 F2F2 的分量加法

(a,b)+(c,d)=(a+b,c+d).(a,b)+(c,d)=(a+b,c+d).

所以例如 (1,1)+(0,1)=(1,0)(1,1)+(0,1)=(1,0)。 这再次是 XOR，但现在是在长度为 22 的字符串上。 挑战再次是提出一个乘法规则。

让我们尝试逆向工程。 假设它以某种方式定义并具有我们想要的所有属性。 对接下来内容至关重要的是，我们还要求乘法中性元素为 (1,0)(1,0)。 这是 F2F2 中通常标识为具有空第二坐标的元素的 11。

让我们找出 (0,1)⋅(0,1)(0,1)⋅(0,1) 是什么。 它肯定 F22F22 其中一个元素。 所以只有四种可能的选择。 它不能是 (0,1)⋅(0,1)=(0,0)(0,1)⋅(0,1)=(0,0)，否则我们会得到 (0,1)=(0,0)(0,1)=(0,0)。 这是我们在本文第一部分中提到的属性：在一个域中，如果 x⋅xx⋅x 等于加法 00 的中性元素，则 x=0x=0。 这里的中性元素是 (0,0)(0,0)，因为我们在 F22F22 中使用分量加法。

另一种可能性是 (0,1)⋅(0,1)=(1,0)(0,1)⋅(0,1)=(1,0)，那么我们可以进行以下推理。

(1,1)⋅(1,1)=((1,0)+(0,1))⋅((1,0)+(0,1))=(1,0)⋅(1,0)+2(1,0)⋅(0,1)+(0,1)⋅(0,1)=(1,0)⋅(1,0)+(0,1)⋅(0,1)=(1,0)+(1,0)=(0,0)(1,1)⋅(1,1)=((1,0)+(0,1))⋅((1,0)+(0,1))=(1,0)⋅(1,0)+2(1,0)⋅(0,1)+(0,1)⋅(0,1)=(1,0)⋅(1,0)+(0,1)⋅(0,1)=(1,0)+(1,0)=(0,0)

出于同样的原因，这很糟糕，我们得到 (1,1)⋅(1,1)=(0,0)(1,1)⋅(1,1)=(0,0) 但 (1,1)(1,1) 与 (0,0)(0,0) 不同。

所以我们只剩下 (0,1)⋅(0,1)(0,1)⋅(0,1) 的两个选项。 要么 (0,1)⋅(0,1)(0,1)⋅(0,1) 等于 (1,1)(1,1)，要么等于 (0,1)(0,1)。 但是与我们给出的那些类似的论点排除了 (0,1)(0,1)。 所以，唯一可能的候选者是

(0,1)⋅(0,1)=(1,1)(0,1)⋅(0,1)=(1,1)

有了这个事实，我们可以构造乘法表的其余部分。 例如

(1,1)⋅(1,1)=(1,0)⋅(1,0)+(0,1)⋅(0,1)=(1,0)+(1,1)=(0,1).(1,1)⋅(1,1)=(1,0)⋅(1,0)+(0,1)⋅(0,1)=(1,0)+(1,1)=(0,1).

这工作正常。 虽然乍一看并不明显，但它满足我们想要的所有属性。 现在有一个乘法规则的候选者，证明很容易但很乏味。 我们将不得不检查所有属性并验证它们是否满足（这是一个有限的检查量）。

符号

让我们引入一个与复数的 a+bia+bi 符号具有相同精神的符号。 与该情况类似，让我们使用 F2F2 在 F22F22 中的标识，并写 00 和 11 来表示 (0,0)(0,0) 和 (1,0)(1,0)。 现在不用像复数那样使用符号 ii，而是让我们使用 xx 来表示 (0,1)(0,1)。 没有真正的原因。 只是 ii 与复数高度相关，我们想强调这与该域无关。 所以现在我们有

(0,0)=0+0x=0(0,0)=0+0x=0

(1,0)=1+0x=1(1,0)=1+0x=1

(0,1)=0+1x=x(0,1)=0+1x=x

(1,1)=1+1x=1+x(1,1)=1+1x=1+x

使用我们刚刚发现的乘法规则，我们得到 x2=1+xx2=1+x。

这个方程式是我们能够通过重复应用它来乘以任何两个元素所需要的，只要出现大于 11 的幂。 例如：

(1+x)x=x+x2=x+1+x=1.(1+x)x=x+x2=x+1+x=1.

具有此加法和乘法的集合 F22F22 具有其符号：它表示为 F4F4，称为 具有四个元素的域。

长度为 33 的二进制字符串

可以使用 F2F2 元素的元组 (a,b,c)(a,b,c) 执行相同的过程。 该集合的元素是 (0,0,0),(1,0,0),(0,1,0),(1,1,0)(0,0,0),(1,0,0),(0,1,0),(1,1,0) 等。它有 88 个元素，我们将用 F32F23 表示它。 我们有成分加法

(a,b,c)+(a′,b′,c′)=(a+a′,b+b′,c+c′)(a,b,c)+(a′,b′,c′)=(a+a′,b+b′,c+c′)

我们可以像以前一样玩游戏并发现一个 F32F23 上的乘法规则，以便它与分量加法一起形成一个域。 在这种情况下，我们甚至可以找到一个使得 (0,1,0)⋅(0,1,0)=(0,0,1)(0,1,0)⋅(0,1,0)=(0,0,1) 成立的。 我们将不展示整个过程。 你可以自己尝试一下！

与之前的情况类似，该域表示为 F8F8，它是具有 88 个元素的唯一域。

符号

我们将 F2F2 标识为 F8F8 中具有空第二和第三坐标的元素。 也就是说，F2F2 是 (0,0,0),(1,0,0)(0,0,0),(1,0,0)。

既然我们有三个坐标，我们需要两个新符号 xx 和 yy 来将元素 (a,b,c)(a,b,c) 写为 a+bx+cya+bx+cy。 但是，由于 (0,1,0)⋅(0,1,0)(0,1,0)⋅(0,1,0) 等于 (0,0,1)(0,0,1)，我们有 x2=yx2=y。 因此，我们只需要一个符号，可以将 (a,b,c)(a,b,c) 写为 a+bx+cx2a+bx+cx2。

如果你像在长度为 22 的二进制字符串的情况下构造乘法规则，你会发现 (0,1,0)⋅(0,0,1)=(1,1,0)(0,1,0)⋅(0,0,1)=(1,1,0)。 使用此符号，即 x3=1+xx3=1+x。 与之前的情况类似。 这个方程式是我们乘以元素所需要的。 例如

(1+x2)(1+x)=1+x+x2+x3=1+x+x2+1+x=x2.(1+x2)(1+x)=1+x+x2+x3=1+x+x2+1+x=x2.

一般情况！

假设我们从 FpFp 开始，其中 pp 是一些素数。 我们可以考虑元组 (a0,a1,…,an−1)(a0,a1,…,an−1) 的集合，所有元组的长度都为 nn，并将该集合称为 FpnFpn。 在那里，我们有分量加法。 定理指出，FpnFpn 上总是存在一个乘法规则，使得它形成一个域！ 此外，所有乘法规则本质上都是相同的。 这意味着存在一个唯一的 pnpn 元素的域。

我们为长度为 22 和 33 的二进制字符串展示的所有内容都适用于此处。 我们可以将每个元素 (a0,a1,…,an−1)(a0,a1,…,an−1) 写为

a0+a1x+a2x2+⋯+an−1xn−1a0+a1x+a2x2+⋯+an−1xn−1

此符号与乘法规则一致，就像以前一样。 此外，对于 FpFp 中的某些元素 bibi，将存在形式为 xn=b0+b1x+⋯+bn−1xn−1xn=b0+b1x+⋯+bn−1xn−1 的相等性。

每个有限域都是这种形式！

域塔

如果我们使用任何有限域 FF 作为构建块，则同样有效。 例如，我们可以从 F=F8F=F8 开始。 我们可以考虑 FF 元素的元组 (a0,⋯,an−1)(a0,⋯,an−1)，所有内容都相同。 FnFn 上总是有一个乘法规则，使其成为一个域。 这对于以小步构建大型扩展非常有用。

举例来说，假设我们需要使用 Fp12Fp12，即具有 p12p12 个元素的域（对于某个素数 pp）。 我们可以通过在 F12pFp12（即 FpFp 的长度为 1212 的元组的集合）上找到一个乘法规则从头开始构造它。

另一种方法如下。 首先构造具有 p6p6 个元素的域 Fp6Fp6。 然后考虑具有 a,b∈Fp6a,b∈Fp6 的元组 (a,b)(a,b)。 该元组集合上存在一个乘法规则，使其成为一个域。 这将是 Fp12Fp12。 这些被称为域塔，是构造有限域的常见方法。

当使用 BLS12-377 或 BLS12-381 曲线时，Fp12Fp12 的情况特别有趣。 它是所有与配对相关的点都被定义的域。

字节集

请注意，F256F256 是所有可能的字节的集合。 它的元素是 F2F2 元素的元组 (a0,a1,…,a7)(a0,a1,…,a7)。 我们用 a0+a1x+a2x2+⋯+a7x7a0+a1x+a2x2+⋯+a7x7 表示它们。 这里的方程是 x8=x4+x3+x+1x8=x4+x3+x+1。

高级加密标准（AES）使用此域作为分组密码的一部分！

总结

就像复数只是实数对一样，有限域的域扩展只是某些 FpFp 元素的元组。 如何提出乘法规则并不明显，但数学家已经证明它总是存在，并且由此产生的域本质上是唯一的，我们没有在这里提及的严格方式。 域扩展在许多证明系统中至关重要，尤其是那些依赖于 Kate-Zaverucha-Goldberg (KZG) 承诺的系统。

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