驱动Binius的域

介绍

通用 zkVM 的发展使得编写可验证的应用程序变得更加容易，它允许开发人员编写高级代码，然后将其编译为 RISC-V 或其他指令集架构（ISA），并在虚拟机之上运行。然后，虚拟机使用证明系统（如 STARKs 或 Groth16）生成简洁的执行证明。证明系统的最新进展已经能够减少证明时间，并且我们正朝着以太坊区块的实时证明方向发展。Binius 是一种证明系统，其开发重点在于如何创建一种对硬件友好的技术。了解硬件的工作原理，一种在其上进行真正快速数学运算的定制证明系统可以产生显着改进。Petra 是第一个利用 Binius 的虚拟机。是什么让 Binius 与众不同，它是如何工作的？

在本文中，我们将回顾 Binius 协议背后的基本数学原理，该协议利用了布尔超立方体 $B_{\ell} = {0, 1}^{\ell}$。我们将专注于二元塔的初等描述和域元素的表示，以及利用其与电路级运算的自然关系的域元素的加法和乘法。在整篇文章中，我们将介绍一些二元塔出现并作为一种技术上有趣的对象而存在的底层材料，即：

• Diamond 和 Posen 在 2023 年发表的论文 "Succint Arguments over Towers of Binary Fields"
• David Cantor 1989 年的开创性论文 "On Arithmetical Algorithms over Finite Fields"
• Wiedemann 1987 年的文章 "An Iterated Quadratic Extension of GF(2)"

有关更多背景材料，请参阅我们之前关于 Binius 第 1 部分的帖子 和 Binius 第 2 部分

域扩展和域元素的表示

在下面的讨论中，我们将把 $F_2 = {0, 1}$ 固定为具有两个元素的域。该域的 $d$ 次有限域扩展可以表征为商环

$F_q \equiv F[X] / \langle f(X) \rangle$

其中 $f$ 是任何不可约多项式 $f \in F_2[X]$，其次数为 $d$：该域恰好有 $q = 2^d$ 个元素，并且由多项式除以 $f$ 的所有余数组成。换句话说，它由次数至多为 $d-1$ 且系数在 $F_2$ 中的多项式组成。此外，此扩展可以看作是基域 $F_2$ 上维度为 $d$ 的向量空间，这是一个非常好的特性。集合

$B_q = {1, X, X^2, \dots, X^{d-1}}$

通常称为“单项式基”，并且在固定此基后，建立了一个同构，用于识别此类多项式及其 $F_2$ 坐标。当域元素被视为多项式时，其加法和乘法运算是模 $f$ 执行的。

例子

考虑多项式 $f(X) = X^2 + X + 1$ 作为 $F_2[X]$ 中的一个元素。$f$ 是不可约的；如果它有一个非平凡因子 $g$，那么 $deg(g) = 1$ 并且由于 $g \in F_2[X]$，那将迫使 $g$ 的根成为 $f$ 的根。由于 $f$ 在基域中没有根，那么我们得出结论 $f$ 是不可约的并且

$F[X] / \langle X^2 + X + 1 \rangle$

确实是 $F_2$ 的 2 次扩展；这意味着它可以被认为是基域上维度为 2 的向量空间。那么，这个向量空间的规范基是

$B_2 = {1, X}$

并且它的所有元素都可以列为 $B_2$ 的元素的线性组合：

$F_4 = {0, 1, X, 1+X}$

$F_4$ 在 $F_2$ 上的坐标表示可以在下表中查看

扩展中的域运算是 $F_2[X]$ 中的环运算，通过考虑非平凡关系 $X^2 + X + 1 = 0 \iff X^2 = 1 + X$ 将其应用到商域。这有时以一种直接的方式解释：现在 $X$ 成为 $f$ 在域扩展 $F_4$ 中的根。

我们观察到，在上一个示例中 $f$ 的不可约性很简单，因为 $f$ 的次数足够低：如果 $deg(f) \le 3$ 那么 $f$ 在 $F[X] \iff f$ 上是不可约的，则 $f$ 在 $F$ 中没有根（这是域理论中的一个定理）。

定义（二次扩展）： 由次数为 2 的不可约多项式进行商运算定义的域扩展称为 二次 扩展。

定义（域塔）： 只要有域 $K$、$E$、$F$ 使得

$K \subset E$ 且 $E \subset F$

我们就说 $E$ 是 $K$ 的扩展 （通常记为 $E | K$），并且 $F$ 是 $E$ 的扩展。将这些扩展放在一起会产生一个 扩展塔，我们将其表示为 $F | E | K$。

事实证明，乍一看，连接域扩展可能看起来很陌生且过于复杂，但最终会产生巨大的成果。

扩展示例：$F_{16}$ 的两种构造

让我们研究 16 个元素的域的两个不同的实现，看看域是如何构造的。

第一个构造： 通过次数为 4 的多项式进行商运算得到 $F_{16}$：

为了构造域 $F_{16}$，我们需要找到一个 $F_2 = {0, 1}$ 上次数为 4 的不可约多项式。其中一个不可约多项式是：

$p(X) = X^4 + X + 1$

为了验证这个多项式在 $F_2$ 上是不可约的，我们需要检查它在 $F_2$ 中没有根 并且 它不能被分解为 $F_2$ 上两个次数为 2 的不可约多项式的乘积。

1. 在 $F_2$ 中没有根：

• $p(0) = 0^4 + 0 + 1 = 1 \neq 0$

• $p(1) = 1^4 + 1 + 1 = 1 + 1 + 1 = 1 \pmod{2} \neq 0$

由于 $p(X)$ 在 $F_2$ 中没有根，因此它没有线性因子 $(X - a)$，其中 $a \in F_2$

2. 无法分解为两个次数为 2 的不可约多项式：

$F_2$ 上唯一的次数为 2 的不可约多项式是 $X^2 + X + 1$。如果 $X^4 + X + 1$ 可以约简为两个次数为 2 的多项式，则它必须是 $(X^2 + X + 1)(X^2 + aX + b)$，其中 $a, b \in F_2$。

展开这个乘积：

$(X^2 + X + 1)(X^2 + aX + b) = X^4 + (a+1)X^3 + (b+a+1)X^2 + (b+a)X + b$

将系数与 $X^4 + 0X^3 + 0X^2 + 1X + 1$ 进行比较：

• $X^3$ 的系数： $a + 1 = 0 \implies a = 1$

• $X^2$ 的系数： $b + a + 1 = 0 \implies b + 1 + 1 = b = 0$

• $X$ 的系数： $b + a = 1 \implies 0 + 1 = 1$ （这是一致的）

• 常数项： $b = 1$

我们有一个矛盾，因为我们发现 $b = 0$ 且 $b = 1$。因此，$X^4 + X + 1$ 不能被分解为 $F_2$ 上两个次数为 2 的不可约多项式。

由于 $p(X) = X^4 + X + 1$ 是 $F_2$ 上次数为 4 的不可约多项式，因此商环

$F_2[X] / \langle X^4 + X + 1 \rangle$

是一个具有 $2^4 = 16$ 个元素的域。

该域的元素可以表示为 $X$ 中次数最多为 3 且系数在 $F_2$ 中的多项式；此外，这些元素的加法是通过将多项式的系数按模 2 相加来完成的，而乘法是通过将多项式相乘 然后 将结果模 $X^4 + X + 1$ 来约简的。这种约简是通过重复使用关系 $X^4 \equiv -X - 1 \equiv X + 1 \pmod{X^4 + X + 1}$ 来实现的。

例如，要将 $\alpha = 1 + X + X^3$ 和 $\beta = X^2 + X^3$ 相乘，

$\alpha \cdot \beta = (1 + X + X^3) \cdot (X^2 + X^3) = X^2 + X^3 + X^3 + X^4 + X^5 + X^6$

通过使用模 2 加法，我们可以消除 $X$ 的三次方，并且通过定义关系式，我们可以替换 $X$ 的所有高于 4 的幂：

$\alpha \cdot \beta = X^2 + (1 + X) + X(1 + X) + X^2(1 + X) = X^2 + 1 + X + X + X^2 + X^2 + X^3$

再次通过模 2 加法，我们得到 $\alpha \cdot \beta = 1 + X^2 + X^3$。

我们将看到，即使很容易理解这种乘法模式的机制，它的效率也很低。我们希望有一种不同的方式来表示域扩展中的元素，以便可以快速有效地完成乘法。

第二个构造：$F_{16}$ 作为二次扩展序列

在这种方法中，我们将通过实现一个以 $F_{16}$ 为顶部的域塔来构造 16 个元素的域；我们将利用二次扩展以及当多项式的次数较低（最多为 3）时，可以通过寻找根来推断它们的不可约性的事实。

步骤 1：$F_4$ 作为 $F_2$ 的扩展：

和以前一样，我们使用 $F_2$ 上的不可约多项式 $p(t) = t^2 + t + 1$。由于扩展 $F_2$ 是连接 $f$ 的根 $X_0$，我们将简单地说

$F_4 = F_2(X_0)$

并且该域的四个元素很简单 $0, 1, X_0, 1+X_0$，其中 $X_0^2 = X_0 + 1$。

步骤 2：$F_{16}$ 作为 $F_4$ 的扩展：

由于 $F_4$ 有 4 个元素，我们需要一个 $F4$ 上次数为 $2$ 的不可约多项式来构造 $F{16}$，并授予 $[F_{16} : F_4] = 2$（参见扩展的次数）；考虑 $F_4$ 上的多项式 $q(t) = t^2 + t + X_0$。要检查不可约性，我们需要看看它在 $F_4 = {0, 1, X_0, 1+X_0}$ 中是否有根。所以，让我们开始逐一检查：

• $q(0) = 0^2 + 0 + X_0 = X_0 \neq 0$
• $q(1) = 1^2 + 1 + X_0 = 1 + 1 + X_0 = 0 + X_0 = X_0 \neq 0$
• $q(X_0) = X_0^2 + X_0 + X_0 = (X_0 + 1) + X_0 + X_0 = X_0 + 1 + 0 = X_0 + 1 \neq 0$
• $q(1+X_0) = (1+X_0)^2 + (1+X_0) + X_0 = (1+X_0^2) + 1 + X_0 + X_0 = 1 + (X_0 + 1) + 1 + 0 = X_0 + 1 + 1 = X_0 \neq 0$

由于 $q(t)$ 的次数为 2 并且在 $F_4$ 中没有根，因此它在 $F_4$ 上是不可约的，并且通过连接 $q$ 的根 $X_1$ 获得的扩展产生

$F_{16} = F_4(Y) = F_2(X_0)(X_1) = F_2(X_0, X_1)$

受以下关系的约束：

• $X_0^2 = X_0 + 1$ （这来自第一个扩展）
• $X_1^2 = X_1 + X_0$ （这来自第二个扩展）

每个步骤实际上都是通过对次数为 2 的不可约多项式进行商运算来定义的，即每个步骤都是 二次扩展。更重要的是，$F_{16}$ 中的每个元素都是基元素以 $F_2$ 为系数的线性组合

${1, X_0, X_1, X_0 \cdot X_1}$

关于坐标的一句话：

让我们计算一下 $F_{16}$ 在 $F_4$ 和基域 $F2$ 上的坐标表示。$F{16}$ 的元素可以写成 $a + bX_1$ 的形式，其中 $a, b \in F4$。由于 $a$ 和 $b$ 各有 4 种选择，因此 $F{16}$ 中有 $4 \times 4 = 16$ 个元素；另请记住，$F_4$ 在 $F_2$ 上的基是 ${1, X0}$，并且 $F{16}$ 在 $F_4$ 上是 ${1, X_1}$。

域理论中有一个著名的定理，塔中上层域的基由下层扩展中基元素的乘积组成。但这里有一个注意事项：我们将考虑有序基。这意味着为了展示一个基，我们不仅必须展示一个跨越向量空间的线性无关子集，而且我们还需要明确这些元素在基中的 顺序。需要此顺序才能使用坐标。考虑到上面的有序基，让我们看一下 $F_{16}$ 中的元素：

单项式基的选择也显示了连续基中的坐标如何相互关联：例如，假设我们取一个元素 $\omega = a + bX1 \in F{16}$，其中 $a, b \in F_4$，我们用坐标 $(a, b)$ 表示 $\omega$。如果我们现在用 $F_2$ 上的基 ${1, X_0}$ 表示 $a$ 和 $b$，那么我们可以通过简单地连接 $a$ 和 $b$ 的坐标来找到 $\omega$ 在 $F_2$ 上的坐标！

为了说明这张表所说的内容，取元素 $\omega = X_0 + X_1$。在 $F_4$ 上，它是 $X_0 \cdot 1 + 1 \cdot X1$，因此坐标是 $[\omega]{F_4} = (X_0, 1)$。

现在，$[X0]{F2} = (0, 1)$ 并且 $[1]{F_2} = (1, 0)$，所以

$[X_0 + X1]{F_2} = (0, 1, 1, 0)$

我们重复先前提到过的内容：每当选择基时，也会选择基元素的顺序；从数学上讲，由相同元素组成但顺序不同的基是不同的基。在本说明中，顺序是以传统方式选择的，从左到右读取基，在我们读取匹配连续扩展时聚合元素。这不是唯一的方法；事实上，反向排序在计算机科学家中很受欢迎。

Wiedemann 塔以及 Diamond 和 Posen 的工作

我们刚刚在 $F_{16}$ 的示例中看到的是 Wiedemann 塔 的一个实例：一系列域扩展，其中每个扩展都是前一个的二次扩展，以这样一种方式表示，即可以通过在某个时刻连接一系列不可约多项式的根来获得扩展的基。在刚才看到的例子中，基很简单

$B = {1, X_0, X_1, X_0X_1}$

并且域元素只是这些符号的 $F_2$ 线性组合：我们通常将它们视为 $F_2$ 上 2 个变量的多项式，其中所有变量的最高次数都为 1。这些多项式通常在密码学上下文中称为“多线性”。这些类型的域扩展和多项式是 Ben Diamond 和 Jim Posen 在他们的提议中实现零知识协议设置的核心，他们提出在特征为 2 的情况下，依赖电路级算术运算以获得更高效的性能：BINIUS。他们的工作中定义的二元塔就像一个迭代二次扩展序列一样定义，灵感来自 Wiedemann 的工作。为了匹配他们的符号集，设置 $T_0 = F_2$，然后递归定义

$T_{k+1} = Tk[X{k+1}] / \langle f_{k+1} \rangle$

其中 $f{k+1}(X{k+1}) = X_{k+1}^2 + XkX{k+1} + 1$；Wiedemann 证明了这个多项式在 $Tk$ 上确实是不可约的，因此它将 $T{k+1}$ 定义为 $T_k$ 的二次扩展。简要写下几个扩展

$F_2 = T_0, F_4 = T1, F{16} = T_2, \dots$

我们通常将 $T_k$ 称为 $T_0$ 的第 $k$-级或扩展；这样的域恰好有 $2^{2k}$ 个元素。在该级别中，元素被描述为 $k$ 个变量 ${X_0, X1, \dots, X{k-1}}$ 中的多项式，这样每个 $X$ 的最高次数都为 1，也就是说，它们是多线性单项式在 $F_2$ 上的线性组合。为简单起见，还有一种极其方便的方法可以指向特定的单项式，它与非负整数的二元展开有关。

为了清楚起见，假设我们需要找到第 $n$-个基元素，我们将其称为 $y_n$。为此，我们只需以 2 为底展开 $n$：

$n = \sum_{i=0} n_i 2^i$, 其中 $n_i \in {0, 1}$

然后设置

$yn = \prod{i: n_i = 1} X_i$

例如，要获得 Wiedemann 塔中的第十个基本元素，首先以 2 为底展开：

$10 = 0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 1 \cdot 2^3$, 或者更简洁地说 $[10]_2 = [1010]$

（你需要记住，计算机科学的惯例是从最高有效数字开始展开，并且元素的计数通常从零开始），然后构建

$y_{10} = X_1X_3$

这种特定的基排序，我们自然地承认，实际上是 字典序，这将允许各种事情：

• 首先，它将允许我们确定一个元素是否属于 $Tk$ 的特定子域；每当与 $k$-级元素关联的坐标向量的最后一半坐标等于零时，我们就会知道它属于 $T{k-1}$
• 先前的事实表明，塔构造通过在坐标向量的后半部分中进行零填充，从而很好地将 $T_{k-1}$ 嵌入到 $T_k$ 中。从计算上讲，将子域中的元素视为该域扩展的元素具有“零成本”。

这些特性使 Wiedemann 塔非常适合于代码和芯片级实现：对于任意扩展，我们都无法从数学上保证我们可以识别元素属于哪个子域。但是，在这种情况下，并且由于这些域的高度结构化的性质，有时可以快速解决该问题。或者更好地说：我们可以轻松地描述扩展的子域。

域运算和乘法问题

这些类型塔的一个有趣的方面是坐标在通常的域运算下的行为方式。

加法

$F_2$ 中的加法（这是在坐标上执行的运算）与 XOR 运算之间的关系是直接且根本的。有限扩展 $T_k$ 中两个元素的加法是通过将它们的相应坐标模 2 相加来执行的。由于模 2 加法等效于 XOR 运算，因此加法是大多数处理器架构中非常快速有效的按位运算。

乘法

现在这里的事情变得棘手了。域元素的乘法可以根据这些元素的表示方式以不同的方式进行。让我们从

以朴素方式乘法：带约简的多项式

乘法中一种更直接的方法是首先将元素表示为多项式，然后将这些多项式相乘，最后将乘积以定义 $F_2$ 扩展的不可约式为模进行约简。

为了说明这一点，考虑 $u, v \in T_2$。让我们慢慢来。

以 $X_1$ 中的多项式与 $T_1$ 中的系数相乘：

$u \cdot v = ((1+X_0) + X_1)(X_0 + X_0X_1) = (1+X_0)X_0 + (1+X_0)X_0X_1 + X_1X_0 + X_1(X_0X_1) = (X_0 + X_0^2) + (X_0 + X_0^2)X_1 + X_0X_1 + X_0X_1^2$

现在，我们替换 $X_0^2 = X_0 + 1$ 和 $X_1^2 = X_1X_0 + 1$：

$= (X_0 + X_0 + 1) + (X_0 + X_0 + 1)X_1 + X_0X_1 + X_0(X_1X_0 + 1) = (2X_0 + 1) + (2X_0 + 1)X_1 + X_0X_1 + X_1X_0^2 + X_0)$

由于我们处于特征为 2 的域中，因此 $2X_0 = 0$。所以，

$= 1 + X_1 + X_0X_1 + X_1(X_0 + 1) + X_0 = 1 + X_1 + X_0X_1 + X_0X_1 + X_1 + X_0 = 1 + X_0 = 1 + X_1 + X_0X_1 + X_1(X_0 + 1) + X_0 = 1 + X_1 + X_0X_1 + X_0X_1 + X_1 + X_0 = 1 + X_0$

因此， $((1 + X_0) + X_1)(X_0 + X_0X_1) = 1 + X_0((1 + X_0) + X_1)(X_0 + X_0X_1) = 1 + X_0$ 在 $T_2$ 中。

正如读者可能已经猜到的那样 - 这需要大量的工作。我们希望有一种更有效的域元素乘法算法，该算法可以从高度结构化的扩展塔中提取。

一种系统地进行域元素乘法的方法是使用类似 Karatsuba 的技术。

#### Wiedemann 塔中的类 Karatsuba 乘法

当应用于有限域扩展（如 Wiedemann 塔的级别）中的元素相乘时，Karatsuba 算法的主要目的是通过增加 **域加法** 和 **子域乘法** 的数量来 **减少较大域中的域乘法次数**，因为它利用了通过 XOR 完成的加法在计算上很便宜的事实。

具体来说，对于在子域上乘两个 1 次多项式，一种朴素的方法将需要在子域中进行四次乘法。Karatsuba 的方法仅用 **三次乘法** 和子域中的少量加法来实现。当递归地应用于塔扩展的多个级别时，这种表面上很小的减少变得非常重要，从而导致亚二次渐近复杂性。

让我们首先描述 Karatsuba 公式，用于将 $T_k$（它是 $X_{k-1}$ 中次数最多为 1 且系数在 $T_{k-1}$ 中的多项式）中的两个元素相乘，首先说明乘法的外观，然后提高我们的眼力：

假设我们需要将 $u = \alpha_0 + \alpha_1X_{k-1}$ 和 $v = \beta_0 + \beta_1X_{k-1}u = \alpha_0 + \alpha_1X_{k-1}$ 和 $v = \beta_0 + \beta_1X_{k-1}$ 相乘，其中 $\alpha_i, \beta_i \in T_{k-1}\alpha_i, \beta_i \in T_{k-1}$，对于 $i = 0, 1i = 0, 1$。那么乘法服从分配律，因此我们正在寻找的乘积是

$u \cdot v = \alpha_1\beta_1X_{k-1}^2 + (\alpha_0\beta_1 + \alpha_1\beta_0)X_{k-1} + \alpha_0\beta_0u \cdot v = \alpha_1\beta_1X_{k-1}^2 + (\alpha_0\beta_1 + \alpha_1\beta_0)X_{k-1} + \alpha_0\beta_0$

- **步骤 1：计算子域 $T_{k-1}$ 中的三个中间乘积。**

这是 Karatsuba 技巧减少乘法的地方。我们没有计算涉及 $\alpha_i\beta_j\alpha_i\beta_j$ 的四个乘积，而是求助于计算三个乘法：

- $P_A = \alpha_0\beta_0P_A = \alpha_0\beta_0$
- $P_B = \alpha_1\beta_1P_B = \alpha_1\beta_1$
- $P_C = (\alpha_0 + \alpha_1)(\beta_0 + \beta_1)P_C = (\alpha_0 + \alpha_1)(\beta_0 + \beta_1)$

请注意，在特征为 2 的情况下，这三个乘积足以产生 $u \cdot vu \cdot v$ 中的系数，因为

$P_A + P_B + P_C = \alpha_0\beta_1 + \alpha_1\beta_0 = MP_A + P_B + P_C = \alpha_0\beta_1 + \alpha_1\beta_0 = M$

我们通常称 $M$ 为“中间项”。这三个乘法和两个加法是在 $T_{k-1}$ 中执行的。

- **步骤 2：使用定义的不可约多项式约简乘积。**

到目前为止，乘积由以下公式给出：

$P_BX_{k-1}^2 + MX_{k-1} + P_AP_BX_{k-1}^2 + MX_{k-1} + P_A$

现在关系 $X_{k-1}^2 = X_{k-2}X_{k-1} + 1X_{k-1}^2 = X_{k-2}X_{k-1} + 1$ 将产生所需乘积的最终表达式：

$u \cdot v = (P_A + P_B) + (M + P_BX_{k-2})X_{k-1}u \cdot v = (P_A + P_B) + (M + P_BX_{k-2})X_{k-1}$

这是对元素的规范多项式表示的最终约简。在这里要指出一些相关的内容。这个计算是如何执行的？

- 如前所述，在子域 $T_{k-1}$ 中计算系数 $P_A + P_BP_A + P_B$ 和 $M + P_BX_{k-2}M + P_BX_{k-2}$。
- 为了计算更大的线性组合，我们必须首先计算乘积

$(M + P_BX_{k-2})X_{k-1}(M + P_BX_{k-2})X_{k-1}$

关键是当将 $T_k$ 视为 $T_0$ 上的向量空间时，乘以 $X_{k-1}$ 实际上是一个自同构，因此一旦我们查看 Wiedemann 塔的方便级别中的元素，就可以通过矩阵乘法获得上述乘积（这里是子域链接在一起的方式获得回报的地方）。显式地，**我们首先将 $M + P_BX_{k-2}M + P_BX_{k-2}$ 解释为上层字段 $T_k$ 的一个元素。在坐标中，这个事实是通过将坐标 $[\cdot]_{k-1}[\cdot]_{k-1}$ 填充零以获得其坐标 $[\cdot]_k[\cdot]_k$ 来表达的：**
$[M + P_BX_{k-2}]_k = [[M + P_BX_{k-2}]_{k-1}:, 0, 0, \cdots 0][M + P_BX_{k-2}]_k = [[M + P_BX_{k-2}]_{k-1}:, 0, 0, \cdots 0]$

如果我们认为 $M + P_BX_{k-2} \in T_kM + P_BX_{k-2} \in T_k$，那么与 $X_{k-1}X_{k-1}$ 相乘可以通过矩阵乘法在坐标中进行：

$[(M + P_BX_{k-2})X_{k-1}]_k = [M + P_BX_{k-2}]_kA_{k-1}[(M + P_BX_{k-2})X_{k-1}]_k = [M + P_BX_{k-2}]_kA_{k-1}$

其中 $A_kA_k$ 是一个矩阵，它**以行为单位**，表示 $T_k$ 的基元素与 $X_{k-1}X_{k-1}$ 的乘积在 $T_k$ 上的坐标。

- 最后的加法在顶层域 $T_k$ 中执行；在坐标中，这仅仅通过 XOR 完成。

## 简要总结一下目前为止的内容：

- **层次结构的连接：** 多线性基（如 Diamond 和 Posen 隐式采用的）的关键见解是，一个元素在 $T_k$ 中的表示仅仅是它在 $T_{k-1}$ 中的系数的连接。这意味着你可以简单地通过分割它的位字符串来“解包”一个元素成它的子元素。这是一个“免费”的操作，除了索引操作之外不涉及任何计算。
- **递归应用：** Karatsuba 算法完美地映射到这种递归结构。这正是该算法被设计成高效工作的方式。
- **用于加法的按位 XOR：** 所有的加法都是坐标向量上的简单按位 XOR ($\oplus\oplus$)。这在现代处理器上非常快，它们可以在一个周期内对整个机器字执行 XOR。
- **已定义的约简：** 不可约多项式 ($X_0^2 = X_0 + 1X_0^2 = X_0 + 1, X_1^2 = X_0X_1 + 1X_1^2 = X_0X_1 + 1, X_2^2 = X_1X_2 + 1X_2^2 = X_1X_2 + 1$) 是 $F_2F_2$ 中的简单三项式或二项式。约简步骤 (例如，$X_1^2 \rightarrow X_0X_1 + 1X_1^2 \rightarrow X_0X_1 + 1$) 转化为系数向量上的线性变换，可以通过几个 XOR 和重新索引来完成。
- **小系数：** 由于该域是 $F_2F_2$，所有的系数 ($a_0, a_1, \dotsa_0, a_1, \dots$) 都是单比特（0 或 1）。这简化了 $M_1M_1$ 函数中的基本乘法，使其非常高效。

## 一个手动扩展的例子

让我们计算 $T_3T_3$ 中两个元素的乘积，即

$u = X_0 + X_1X_2$ 和 $v = 1 + X_1 + X_0X_2u = X_0 + X_1X_2$ 和 $v = 1 + X_1 + X_0X_2$

使用上述算法。在进一步深入之前，仅仅因为我们想避免在递归中走得太深，我们可以务实地构建“乘以 $X_0X_0$”映射的矩阵。这个矩阵是

0 1 1 1 0 1 1 1

并有助于构建一个完整的乘法表；要将 $\gamma\gamma$ 乘以 $X_0X_0$，我们计算

$[\gamma]_1 \cdot 0111 = [\gamma \cdot X_0]_1[\gamma]_1 \cdot 0111 = [\gamma \cdot X_0]_1$

对于一个覆盖 $T_1T_1$ 中所有可能的域元素乘法的完整乘法表，我们求助于线性性和上面的小工具。

让我们开始吧。记住 $T_3T_3$ 是一个具有 $2^{2^3} = 2^8 = 2562^{2^3} = 2^8 = 256$ 个元素的域，作为 $F_2 = T_0F_2 = T_0$ 上的向量空间，它的维度是 8；它的多线性基是

$\{1, X_0, X_1, X_0X_1, X_2, X_0X_2, X_1X_2, X_0X_1X_2\}\{1, X_0, X_1, X_0X_1, X_2, X_0X_2, X_1X_2, X_0X_1X_2\}$

我们将用坐标进行 $u$ 和 $v$ 的乘积。首先，

$[u]_3 = (0, 1, 0, 0, 0, 0, 1, 0)$ 和 $[v]_3 = (1, 0, 1, 0, 0, 1, 0, 0)[u]_3 = (0, 1, 0, 0, 0, 0, 1, 0)$ 和 $[v]_3 = (1, 0, 1, 0, 0, 1, 0, 0)$

是 $u$ 和 $v$ 在 $T_3T_3$ 的多线性基中的坐标。在执行 Karatsuba 算法之前，我们将以矩阵形式显示两组坐标，并提示一个分区，对应于两者作为塔中最后扩展的元素的规范描述。这是

$(uv)_3 = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \beta_0 \\ \beta_1 \end{pmatrix}(uv)_3 = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \beta_0 \\ \beta_1 \end{pmatrix}$

我们在这里利用了我们可以将 $u$ 和 $v$ 写在前一个扩展 $T_2T_2$ 上的事实：

$u = \alpha_0 + \alpha_1X_2$ 和 $v = \beta_0 + \beta_1X_2u = \alpha_0 + \alpha_1X_2$ 和 $v = \beta_0 + \beta_1X_2$

对于某些 $\alpha_i, \beta_j \in T_2\alpha_i, \beta_j \in T_2$。回想一下，这个域的维度是 4，并且之前的矩阵分区已经给了我们 $T_2T_2$ 坐标在 $T_0T_0$ 上的坐标！这是二进制塔的多线性基中非常酷的特性！我们现在准备好继续使用 Karatsuba 算法。

- **第一步：** 我们继续计算乘积

1. $P_A = \alpha_0\beta_0P_A = \alpha_0\beta_0$
2. $P_B = \alpha_1\beta_1P_B = \alpha_1\beta_1$
3. $P_C = (\alpha_0 + \alpha_1)(\beta_0 + \beta_1)P_C = (\alpha_0 + \alpha_1)(\beta_0 + \beta_1)$
4. $P_BX_1P_BX_1$

其中**所有这些元素都属于子域 $T_2T_2$，并且在其中进行运算。** 为了做到这一点，我们需要对每个需要的乘积深入一层。让我们谨慎地进行。

i. 为了计算 $P_APA$，我们将 **$T_2T_2$ 上的坐标解释为 $T_0T_0$ 上的坐标** 就像在上一层一样，并写出

$(\alpha_0\beta_0)_2 = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_{00} \\ \alpha_{01} \\ \beta_{00} \\ \beta_{01} \end{pmatrix}(\alpha_0\beta_0)_2 = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_{00} \\ \alpha_{01} \\ \beta_{00} \\ \beta_{01} \end{pmatrix}$

在这种情况下应用 Karatsuba 算法需要使用我们之前提到的乘法表，

- $P'_A = \alpha_{00} \cdot \beta_{00}P'_A = \alpha_{00} \cdot \beta_{00}$，在 $T_1T_1$ 坐标中，这是乘积 $0, 1 \times 1, 0 = 0, 10, 1 \times 1, 0 = 0, 1$
- $P'_B = \alpha_{01} \cdot \beta_{01}P'_B = \alpha_{01} \cdot \beta_{01}$，在 $T_1T_1$ 坐标中，这是乘积 $0, 0 \times 1, 0 = 0, 00, 0 \times 1, 0 = 0, 0$
- $P'_C = (\alpha_{00} + \alpha_{01}) \cdot (\beta_{00} + \beta_{01})P'_C = (\alpha_{00} + \alpha_{01}) \cdot (\beta_{00} + \beta_{01})$，在 $T_1T_1$ 坐标中，这是乘积 $0, 1 \times 0, 0 = 0, 00, 1 \times 0, 0 = 0, 0$ (在每个因子中完成必要的加法后)
- 最后是不寻常的 $P'_BX_0P'_BX_0$ 项的乘积：

$0, 0 \times 0111 = 0, 00, 0 \times 0111 = 0, 0$

现在是构建 $T_2T_2$ 中元素 $\alpha_0\beta_0\alpha_0\beta_0$ 的时候了；现在是基的特殊选择发挥作用的地方（再次）：**$T_1T_1$ 的元素进入 $T_2T_2$ 的方式是根本性的，并且在计算上至关重要：要在上面的扩展中查看它们，我们只需在其 $T_1T_1$ 坐标的末尾填充零以获得一个 4 位字符串。**

根据提出的算法，

$\alpha_0\beta_0 = (P'_A + P'_B) + (M + P'_BX_0)X_1\alpha_0\beta_0 = (P'_A + P'_B) + (M + P'_BX_0)X_1$

的坐标表达式可以逐步重建。**首先在** $T_1T_1$ **中相加，然后**填充：

$$[P'_A + P'_B]^1 = \boxed{0, 1} + \boxed{0, 0} = \boxed{0, 1} \implies [P'_A + P'_B]^2 = \boxed{0, 1, 0, 0}$$

然后，是棘手的部分：视为 $T_1T_1$ 中的元素，

$[P'_BX_0]_1 = 0, 0 \implies [M + P'_BX_0]_1 = 0, 1 + 0, 0 = 0, 1[P'_BX_0]_1 = 0, 0 \implies [M + P'_BX_0]_1 = 0, 1 + 0, 0 = 0, 1$

**在将其与 $X_1X_1$ 相乘之前，我们通过在其末尾填充零将此元素嵌入到 $T_2T_2$ 中。** 乘以 $X_1X_1$ 通过矩阵乘法完成

$[(M + P'_BX_0) \cdot X_1]_2 = 0, 1, 0, 0 \times \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} = 0, 0, 0, 1[(M + P'_BX_0) \cdot X_1]_2 = 0, 1, 0, 0 \times \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} = 0, 0, 0, 1$

最后，执行加法，我们得到

$0, 1, 0, 0 + 0, 0, 0, 1 = 0, 1, , 0, 10, 1, 0, 0 + 0, 0, 0, 1 = 0, 1, , 0, 1$

这意味着 $P_A = \alpha_0\beta_0 = X_0 + X_0X_1 \in T_2P_A = \alpha_0\beta_0 = X_0 + X_0X_1 \in T_2$

- 一旦我们详细解释了第一种情况，我们继续计算 $P_B:P_B:$

$(\alpha_1\beta_1)_2 = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_{10} \\ \alpha_{11} \\ \beta_{10} \\ \beta_{11} \end{pmatrix}(\alpha_1\beta_1)_2 = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} \alpha_{10} \\ \alpha_{11} \\ \beta_{10} \\ \beta_{11} \end{pmatrix}$

我们将计算 $\alpha_1\beta_1\alpha_1\beta_1$，在递归中向下一层，将其在 $T_2T_2$ 中的坐标视为其在 $T_0T_0$ 中的坐标，就像之前一样：

1. $P'_A = \alpha_{10} \cdot \beta_{10}P'_A = \alpha_{10} \cdot \beta_{10}$，在 $T_1T_1$ 坐标中，这是乘积 $0, 0 \times 1, 0 = 0, 00, 0 \times 1, 0 = 0, 0$
2. $P'_B = \alpha_{11} \cdot \beta_{11}P'_B = \alpha_{11} \cdot \beta_{11}$，在 $T_1T_1$ 坐标中，这是乘积 $1, 0 \times 0, 0 = 0, 01, 0 \times 0, 0 = 0, 0$
3. $P'_C = (\alpha_{10} + \alpha_{11}) \cdot (\beta_{10} + \beta_{11})P'_C = (\alpha_{10} + \alpha_{11}) \cdot (\beta_{10} + \beta_{11})$，在 $T_1T_1$ 坐标中，这是乘积 $1, 0 \times 0, 1 = 0, 11, 0 \times 0, 1 = 0, 1$ (在每个因子中完成必要的加法后)
4. 最后，我们有 $P'_BX_0P'_BX_0$ 项（我们省略了写下矩阵乘积，因为从读取坐标来看，这相当简单和直观）：

$0, 0 \times 0, 1 = 0, 00, 0 \times 0, 1 = 0, 0$

有了这些，我们准备好将 $\alpha_1\beta_1\alpha_1\beta_1$ 重构为 $T_2T_2$ 中的元素。

$\alpha_1\beta_1 = (P'_A + P'_B) + (M + P'_BX_0)X_1\alpha_1\beta_1 = (P'_A + P'_B) + (M + P'_BX_0)X_1$

的坐标表达式可以从 2 位字符串重建如下：**首先，相加然后填充。** 我们得到

$[P'_A + P'_B]^1 = 0, 0 + 0, 0 = 0, 0 \implies [P'_A + P'_B]^2 = 0, 0, 0, 0[P'_A + P'_B]^1 = 0, 0 + 0, 0 = 0, 0 \implies [P'_A + P'_B]^2 = 0, 0, 0, 0$

记住填充以在 $T_2T_2$ 坐标中查看它们。然后，是棘手的部分：视为 $T_1T_1$ 中的元素，

$[P'_BX_0]_1 = 0, 0 \implies [M + P'_BX_0]_1 = 0, 1 + 0, 0 = 0, 1[P'_BX_0]_1 = 0, 0 \implies [M + P'_BX_0]_1 = 0, 1 + 0, 0 = 0, 1$

**在将其与 $X_1X_1$ 相乘之前，我们通过在其末尾填充零将此元素嵌入到 $T_2T_2$ 中。** 然后，矩阵乘法：

$[(M + P'_BX_0)X_1]_2 = 0, 1, 0, 0 \times \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} = 0, 0, 0, 1[(M + P'_BX_0)X_1]_2 = 0, 1, 0, 0 \times \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} = 0, 0, 0, 1$

然后我们执行加法以获得

$0, 0, 0, 0 + 0, 0, 0, 1 = 0, 0, , 0, 10, 0, 0, 0 + 0, 0, 0, 1 = 0, 0, , 0, 1$

这意味着 $P_B = \alpha_1\beta_1 = X_0X_1 \in T_2P_B = \alpha_1\beta_1 = X_0X_1 \in T_2$

现在我们想计算 $P_C = (\alpha) + \alpha_1)(\beta_0 + \beta_1)P_C = (\alpha) + \alpha_1)(\beta_0 + \beta_1)$。通过查看 $u$ 和 $v$ 的坐标表达式，可以快速完成其前半部分和后半部分的加法，现在我们有

$(\alpha_0 + \alpha_1\beta_0 + \beta_1)_2 = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}(\alpha_0 + \alpha_1\beta_0 + \beta_1)_2 = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}$

我们将计算 $P_CPC$，在递归中向下一层，将其在 $T_2T_2$ 中的坐标视为其在 $T_0T_0$ 中的坐标，就像之前一样：

1. $P'_A = a \cdot cP'_A = a \cdot c$，在 $T_1T_1$ 坐标中，这是乘积 $0, 1 \times 1, 1 = 1, 00, 1 \times 1, 1 = 1, 0$
2. $P'_B = b \cdot dP'_B = b \cdot d$，在 $T_1T_1$ 坐标中，这是乘积 $1, 0 \times 1, 0 = 1, 01, 0 \times 1, 0 = 1, 0$
3. $P'_C = (a + b) \cdot (c + d)P'_C = (a + b) \cdot (c + d)$，在 $T_1T_1$ 坐标中，这是乘积 $1, 1 \times 0, 1 = 1, 01, 1 \times 0, 1 = 1, 0$ (在每个因子中完成必要的加法后)
4. 最后，我们有 $P'_BX_0P'_BX_0$ 项：

$1, 0 \times 0, 1 = 0, 11, 0 \times 0, 1 = 0, 1$

有了这些，我们准备好将 $P_CPC$ 重构为 $T_2T_2$ 中的元素。

$P_C = (P'_A + P'_B) + (M + P'_BX_0)X_1P_C = (P'_A + P'_B) + (M + P'_BX_0)X_1$

的坐标表达式可以从 2 位字符串重构如下：**首先相加，然后填充**。由于我们已经这样做了几次，我们允许一些加速：

$[P'_A + P'_B]_2 = 1, 0, 0, 0 + 1, 0, 0, 0 = 0, 0, 0, 0[P'_A + P'_B]_2 = 1, 0, 0, 0 + 1, 0, 0, 0 = 0, 0, 0, 0$

然后，是棘手的部分：视为 $T_1T_1$ 中的元素，

$P'_BX_0 = 0, 1 \implies M + P'_BX_0 = 1, 0 + 0, 1 = 1, 1P'_BX_0 = 0, 1 \implies M + P'_BX_0 = 1, 0 + 0, 1 = 1, 1$

**在将其与 $X_1X_1$ 相乘之前，我们通过在其末尾填充零将此元素嵌入到 $T_2T_2$ 中。** 我们现在通过简单地将其系数向左移动两位，同时用零填充前两个槽位来在上层扩展中执行乘积：

$[M + P'_BX_0]_2 = 1, 1, 0, 0$, 然后 $[(M + P'_BX_0)X_1]_2 = 0, 0, 1, 1[M + P'_BX_0]_2 = 1, 1, 0, 0$, 然后 $[(M + P'_BX_0)X_1]_2 = 0, 0, 1, 1$

我们得到 $[P_C]_2 = 0, 0, 1, 1[P_C]_2 = 0, 0, 1, 1$，也就是说，$P_C = X_1 + X_0X_1 \in T_2P_C = X_1 + X_0X_1 \in T_2$

这一层中的最后一个分支是计算 $P_BX_1P_BX_1$；此乘积发生在 $T_2T_2$ 子域中。在坐标中，我们有

$[P_BX_1]_2 = 0, 1, 1, 1[P_BX_1]_2 = 0, 1, 1, 1$

- **第二步：** 通过执行加法来重构

我们现在准备好用 Karatsuba 的方法构建 $u \cdot vu \cdot v$：

$u \cdot v = (P_A + P_B) + (M + P_BX_1)X_2u \cdot v = (P_A + P_B) + (M + P_BX_1)X_2$

让我们用坐标进行。在其他任何事情之前，让我们首先显示我们需要组合的所有元素，这样我们就不会搞砸了。

1. $P_A = X_0 + X_0X_1 \in T_2 \Longleftrightarrow [P_A]_2 = 0, 1, 0, 1P_A = X_0 + X_0X_1 \in T_2 \Longleftrightarrow [P_A]_2 = 0, 1, 0, 1$
2. $P_B = X_0X_1 \in T_2 \Longleftrightarrow [P_B]_2 = 0, 0, 0, 1P_B = X_0X_1 \in T_2 \Longleftrightarrow [P_B]_2 = 0, 0, 0, 1$
3. $P_C = X_1 + X_0X_1 \in T_2 \Longleftrightarrow [P_C]_2 = 0, 0, 1, 1P_C = X_1 + X_0X_1 \in T_2 \Longleftrightarrow [P_C]_2 = 0, 0, 1, 1