Additive FFT：背景

警告：这篇文章比其他文章更偏重数学。

介绍

在本文中，我们将继续研究 二元域塔，其动机是 Diamond 和 Posen 提出的在 特征 2 的域上工作的完整协议 BINIUS。之前我们介绍了二元域塔中域元素的基本算术，即 Wiedemann 对 $F_2$ 的迭代二次扩展。我们着手解决在此类域中评估和插值多项式的问题，并考虑密码学应用。设计一种智能高效的算法来进行多项式求值将为在特征 2 中高效实现 Reed-Solomon 编码打开大门，而 Reed-Solomon 编码是多项式承诺的关键组成部分。

关于多项式乘法的通用问题

一旦我们了解了 Wiedemann 二元塔的结构，很自然地会想知道如何评估或将此塔上的函数相乘。对于我们的目标而言，这很重要，因为在基本域的巧妙选择的子集（例如，nn 次单位根）上进行多项式求值是使用 Reed-Solomon 技术对消息进行编码的基础。鉴于此，多项式求值的问题 非常接近 Reed-Solomon 编码的问题。

可以想到一种用于多项式乘法的有效方法：快速傅里叶变换 算法。它采用了著名的方案

evaluate⟶multiply⟶interpolateevaluate⟶multiply⟶interpolate

用更专业的术语来说，对于熟悉的读者，“多项式求值”代表“取多项式的 FFT”，乘法意味着“逐点乘以它们的 FFT”，而插值则表示“取结果的逆 FFT”。这种通用方案使我们能够绕过像在高中一样，将两个多项式相乘并应用分配律的计算成本。这些“求值”和“插值”步骤通常涉及矩阵乘法；每当我们用本原 nn 次单位根的幂来求多项式 ff 的值，并且 nn 是 2 的幂时，就会有一个递归算法可用，并且所有这些都可以快速完成，比如 $O(nlog(n))$。显然，这一定是数学史上最被记录的事实之一；文献比比皆是。

那么在这里应用 FFT 怎么样？嗯，这里有个问题。在有限域的上下文中，“单位根”可能不容易存在，或者找到足够数量的单位根可能需要在更大、更复杂的扩展域中工作。这种根本性的局限性使得标准 FFT 对于这些特定域类型来说要么不切实际，要么非常慢。

正特征扩展塔的通用框架

为了克服这个问题，我们研究了 David Cantor 1989 年发表的 "关于有限域上的算术算法"。他在那里开发了一种 FFT 的类似物，该类似物在基本域的加法子群上运行，而不是在乘法子群上运行；由于现在我们处理的是加法而不是群元素的乘法，因此该方案通常被称为“加法 FFT”。Cantor 找到了单位根的类似物，并像在经典 FFT 案例中一样，将问题分解为一个可以通过递归解决的较小问题。好消息是这些加法子群不过是 $F_p$ 向量子空间，与 Wiedemann 的工作以及 Diamond 和 Posen 的提议 中出现的熟悉的子域密切相关。

构建加法 FFT 的关键对象是线性化多项式的概念； 它们是一类特殊的多项式，由于它们相对于基本有限域中的加法和标量乘法的“线性”性质，因此表现出非常有趣的性质。线性化多项式的单项式的次数都是 qq 的幂，即 $q^r$； 这是一个形式为（请查看文末的附录）：

$L(x) = \sum_{i=0}^{d} a_i x^{q^i}$

其中 $a_i \in Fq$ （在本次讨论中，假设 pp 是素数，并且 $q = p^n$ 对于某个自然数 nn）。这些多项式的主要性质是，由于我们正在模 pp 运算，其行为就像线性代数意义上的线性变换一样。 也就是说，对于任何 $u,v \in F{q^n}$ 和 $c \in F_q$，它们都满足：

• $L(u+v) = L(u) + L(v)$
• $L(cu) = cL(u)$

每当我们有一个线性化多项式 LL 时，它的根（零点）的集合_形成 $Fq$ 上的向量空间（称为核）：

$Ker(L) = {v \in F{q^n} : L(v) = 0} \subset F{q^n}$

这一事实源于线性代数的一般理论； 这意味着根的线性组合仍然是 LL 的根。 最后，线性化多项式的形式（以及刚刚讨论的线性性）提供了一个非常简洁的属性：线性化多项式的组合再次线性化。 这是 Cantor 对正特征域塔描述的支柱。

素特征的扩展塔

为了简洁起见，我们将专注于一个非常简单但重要的例子，它将推动我们对 Cantor 的加法 FFT 工作的理解； 为此，固定一个素数 pp，如果 $\tilde{F}$ 是 $F_p$ 的 代数闭包（例如，复数 CC 是实数 RR 的代数闭包），则取线性化多项式

$S(t) = t^p - t$

从上面讨论的基本定义中，我们得到了许多对象：

• 考虑 SS 与自身的连续组合，得到线性化多项式的集合

$Sm(t) = S \circ S \cdots \circ S(t) = S(S{m-1}(t))$

• 为了便于表示，设置 $W_1 = Ker(S) = F_p$ 和 $W_m = Ker(S_m)$：$S_m$ 的根的集合
• 这是所有机制开始运作的地方，因为对于所有 mm，以下各项都为真：

1. $W_{m-1} \subset W_m$
2. $S: Wm \rightarrow W{m-1}$ 是一个满射函数
3. $W_{m-1}$ 在 $W_m$ 中具有 余维 1

最后这一项在 Cantor 想法的结构中起着非常重要的作用：这意味着如果我们把 $Wm$ 想象成一块巧克力，那么它也可以被认为是 $W{m-1}$ 的 pp 个不相交副本的并集：画一个矩形并将其称为 $Wm$，然后将其分成 pp 个形状和大小相等的部分。 每一个都是 $W{m-1}$ 的副本！

一旦掌握了这个（非常）简短的总结，以下是好东西的来源。一个关键的观察结果是，每当 $m = p^k$ 时，由于我们模 pp 进行运算，因此所涉及的线性化多项式具有非常简洁的形式：

$S_{p^k}(t) = t^{p^k} - t$

它们被称为是稀疏的，因为它们只有少数系数； 这在稍后计算多项式除法的复杂度时会很有用。 它的根的集合形成一个恰好有 $p^k$ 个元素的域，因此回顾列出的属性项，我们得到的是 $F_p$ 的扩展塔：

$W_0 \subset Wp \subset W{p^2} \subset \dots W_{p^k} \subset \dots$

在每一步中，我们都有 pp 次域扩展 $[W{p^k}:W{p^{k-1}}] = p$。 映射 $S: W{p^k} \rightarrow W{p^{k-1}}$ 的满射性意味着对于每个 $k \geq 1$ 和每个 $u{k-1} \in W{p^{k-1}}$，始终存在一个元素 $uk \in W{p^k} - W_{p^{k-1}}$ 使得

$S(uk) = u{k-1}$

这将带来一个非常熟悉的结果。

设置 $p = 2$，我们恢复 Wiedemann 的二元域塔：

$W_0 \subset W2 \subset W{2^2} \subset \dots W_{2^{2k}} \subset \dots$

我们通过承认符号 $W_{2^{2k}} = T_k$ 的等价性来识别它。

此外，映射 SS 的满射性允许找到塔的每个级别的生成元和基。 明确地，

• 塔的第一个生成元设置为 1。
• 第二个生成元是满足 $S(u_0) = 1$ 的元素 $u_0$。 请注意，这等效于 $u_0$ 是 $X^2 + X + 1$ 的根。 很容易检查，由于该多项式在 $F_2$ 中没有根，因此 $u_0 \notin F_2$。
• 然后将第三个生成元定义为 $S(u_1) = u_0$。 这意味着 $u_1^2 + u_1 = u_0$ 或等效地 $u_1^2 + u_1 + u_0 = 0$。 同样，这意味着 $u_1$ 是 $X^2 + X + u_0 \in T_1[X]$ 的根。 很容易检查，该多项式在 $T_1$ 中没有根，因此 $u_1 \notin T_1$。
• 对于 $k > 1$，其余元素由递归关系 $S(uk) = u{k-1}$ 定义，并且也由一个域论关系 $u_k^2 + uk + u{k-1} = 0$ 定义。

在这些生成元的基础上，Cantor 然后根据 mm 的以 22 为基数（二进制）的展开定义基元素 $y_m$，模仿了 Wiedemann 二元塔中元素域乘法中自然利用的内容。 明确地，如果我们写下 mm 的二进制展开

$m = mk 2^k + m{k-1} 2^{k-1} + \cdots + m_0 2^0$

其中 $m_i \in {0, 1}$ 是 mm 的位，则：

$y_m = u_0^{m_0} u_1^{m_1} \cdots u_k^{m_k}$.

为了让我们更好地理解，我们举例说明

• 基元素示例：

1. $y_0 = 1$（对于 $m = 0$，所有 $m_i = 0$）

2. $y_1 = u_0$（对于 $m = 1$，二进制为 $1_2$，因此 $m_0 = 1$）

3. $y_2 = u_1$（对于 $m = 2$，二进制为 $10_2$，因此 $m_1 = 1$）

4. $y_3 = u_0 u_1$（对于 $m = 3$，二进制为 $11_2$，因此 $m_0 = 1, m_1 = 1$）

5. $y_4 = u_2$（对于 $m = 4$，二进制为 $100_2$，因此 $m_2 = 1$）

6. 通常，$y_{2^r} = u_r$ 对于 $r = 0, 1, 2, \dots$

$Tk$ 的这个显式基直接对应于 Diamond 和 Posen 所说的 Wiedemann 塔 $T\iota$ 的“多线性基”。 他们声明，对于 $T_\iota$，单项式集合 $1, X_0, X_1, X_0 \cdot X_1, \dots, X0 \cdot \dots X{\iota-1}$ 构成一个基，其中他们的 $X_i$ 有效地充当 Cantor 的 $ui$。 重要的是要注意，Diamond 论文中的 Wiedemann 塔生成元使用略有不同的关系：$X{j+1}^2 + X_{j+1} + X_j = 0$

尽管生成元关系存在这些差异，这些迭代二次扩展的底层代数结构与 Cantor 用于有效基表示和算术的通用框架一致。

加法 FFT 如何工作：用于多项式求值的递归“分而治之”策略

Cantor 加法 FFT 的核心机制是一个递归的“分而治之”过程，它反映了传统 FFT 算法的效率原则。 在这里，我们将首先概述用 $F_p$ 中的系数评估度数为 $n = p^m$ 的多项式 aa 的问题。 在下文中，我们将保留前面部分中使用的符号。

• 设置评估集：子空间 ($W_m$)：

1. 主要目标是在 $W_m$ 的所有 $p^m$ 元素处评估度数至多为 $n = p^m$ 的多项式 $a(t)$； 在这种意义上，子空间 $W_m$ 扮演着传统 FFT 算法中的 nn 次单位根的角色。

2. 至关重要的是，$Wm$ 可以划分为 $W{m-1}$ 的 pp 个较小的、不相交的“陪集”。 这允许问题的分层分解，就像 nn 为 2 的幂的经典情况一样。 更具体地说，我们知道 SS 是将 $Wm$ 映射到 $W{m-1}$ 的 $F_p$ 线性映射，并且该图像的余维为 1。 这确保存在一个元素 $u \in W_m$ 使得

$Wm = \langle u \rangle \oplus W{m-1}$

由于 $F_p$ 恰好有 pp 个元素，因此

$Wm = \bigcup{\alpha \in Fp} (\alpha \cdot u + W{m-1})$

其中这个并集是不相交的，并且每个子集只是 $W_{m-1}$ 的平移。 为简单起见，我们将采用以下表示法：

$\alpha \cdot u + W{m-1} = W{m-1}^\alpha$

并观察到该集合恰好有 $p^{m-1}$ 个元素，因为 $W{m-1}$ 是 $S{m-1}(t)$ 的根的集合，其度数为 $p^{m-1}$。

• 递归步骤：分解问题：
  1. 现在，为了在 $Wm$ 上评估 $a(t)$，只需知道 $a(t)$ 在每个陪集 $W{m-1}^\alpha$ 处的值就足够了。 由于这些陪集有 $p^{m-1}$ 个元素，因此如果我们能将这个问题简化为在 $W_{m-1}^\alpha$ 上评估度数严格小于 deg(a)deg(a) 的多项式 $b\alpha$ 的问题，那将是太棒了； 理想情况下，deg($b\alpha$) < $p^{m-1}$。

2. 为了掌握其中一个 $c_\alpha$，以下观察结果派上用场：

   a. $W{m-1}$ 是 $p^{m-1}$ 次多项式 $S{m-1}(t)$ 的根的集合

   b. 该多项式的平移将消失在 $W_{m-1}^\alpha$ 上：

   $S{m-1}^\alpha(t) = S{m-1}(t - \alpha \cdot u)$

   别相信我们，自己检查一下。

   c. 因此，代数基本定理指出 aa 除以 $S_{m-1}^\alpha$ 的商的余数是一个度数严格小于 $p^m$ 的多项式，并且

   $a(t) = Q(t) S{m-1}^\alpha(t) + b\alpha(t)$

   成立。 特别是，每当 $w \in W_{m-1}^\alpha$ 时，

   $a(w) = Q(w) \cdot 0 + b_\alpha(w)$

   这意味着在 $W{m-1}^\alpha$ 上 $a \equiv b\alpha$。

3. 然后，该算法递归调用自身，以评估其对应的较小子空间 $W{m-1}^\alpha$ 上的每个 $b\alpha(t)$。

   • 基本情况：

1. 这种递归分解一直持续到多项式 $b_i(t)$ 达到 0 度，这意味着它们变成常数。

2. 这些产生的常数是原始多项式 $a(t)$ 在 $W_m$ 中的点处的期望函数值

逆过程：插值

Cantor 还概述了逆运算，称为插值。 如果已知多项式在 $W_m$ 内所有点的值，则可以反转加法 FFT 算法的步骤来重构原始多项式的系数。 这个逆过程涉及类似的反向执行的除法和求和技术。

计算成本和效率

Cantor 严格分析了他的算法的计算复杂度，将运算分为两种类型：

- A 运算（类似加法）： 这些运算的计算成本与底层域 FF 中的加法相当。

- M 运算（类似乘法）： 这些运算的计算成本与底层域 FF 中的乘法相当。

为了评估 $W_m$ 所有点上的度数 < $n = p^m$ 的多项式：

1. A 运算的总数约为 $O(n(log n)^{1 + log_p((p+1)/2)})$. 对于 $p = 2$，这简化为大约 $O(n(log n)^{1.585})$.

2. M 运算的总数约为 $O(n log n)$.

总结

总之，向量子空间是加法 FFT 运行的“域”。 该算法递归地划分它们并使用线性化多项式（和 Frobenius 自同构）的线性性质来关联不同子空间上的求值，从而实现高效的多点求值和插值。

附录 - 证明和想法

在这里，我们总结了本文中提到的大多数关于线性化多项式的证明、定义和技术细节。 我们从第一个定义开始，并推导出一些采用的属性。

定义（线性化多项式） 有限域 $F_q$ 上的线性化多项式具有以下一般形式：

$L(x) = \sum_{i=0}^{d} a_i x^{q^i}$

其中 $a_i \in F_q$

在这里，我们将它们的主要属性收集为一个条目列表； 其中大多数是容易证明的事实，可以作为鼓舞人心的练习（也提醒我们基本线性代数实际上有多重要）：

- 它们是线性变换： 如果 $L(x)$ 是一个系数在 $Fq$ 中的线性化多项式，则从 $F{q^n}$ 到自身的映射 $x \mapsto L(x)$ 是一个线性变换，考虑到这个扩展是 $Fq$ 上的 n 维向量空间。 这意味着对于任何 $u, v \in F{q^n}$ 和 $c \in F_q$：

• $L(u+v) = L(u) + L(v)$

• $L(cu) = cL(u)$

（此属性源于 qq 个元素的域的特征，该域是多项式 $X^q - X$ 的 分裂域。） 由于 LL 是一个线性映射，因此它的根的集合形成 $F_q$ 上的向量空间：

$Ker(L) = {v \in F{q^n} : L(v) = 0} \subset F{q^n}$

• 组合的不可思议的影响： 通常，多项式的组合会产生一个新的多项式，并且在一般设置中不能说太多。 但是，由于线性化多项式可以被视为线性映射，因此会产生一些惊人的后果：

  1. 从它们的定义来看，线性化多项式可以被视为与 $x^q$ 预先组合的普通多项式。 也就是说，$F_q$ 上的线性化多项式与 $Fq[x]$ 中的“普通”多项式之间存在对应关系。 对于线性化多项式 $L(x) = \sum{i=0}^{d} ai x^{q^i}$，我们关联一个 "qq-常规" 多项式 $l(y) = \sum{i=0}^{d} a_i y^i$。
  2. 从它们的定义和线性性质也可以看出，两个线性化多项式的组合也是一个线性化多项式。 这种二元运算是非交换的，但相对于多项式加法是可分配的。
  3. 如果我们将组合解释为非交换乘法，那么可以设计出除法概念的类似物：我们将说 LL 象征性地除 MM，如果存在一个线性化多项式 RR 使得

  $M(X) = L \circ N(X)$

  4. 不仅如此，线性化多项式、符号可除性及其 qq-常规之间也存在非常显着的联系：$L(x)$ 象征性地除 $M(x)$ 当且仅当 $\ell(y)$ 在普通意义上除 $m(y)$。
  5. 线性化多项式 $L(x)$ 在组合上是不可约的，当且仅当其相关的 qq-常规多项式 $l(y)$ 在 $F_q$ 上是不可约的。 重要的是要注意，组合上不可约的线性化多项式在普通意义上_始终_是可约的（它具有因子 xx）。
• 关于扩展塔的构建，线性化多项式 $S(t) = t^p - t$ 的连续组合

$Sm(t) = S \circ S \cdots \circ S(t) = S(S{m-1}(t))$

产生算法在其上定义的子集。 从线性映射的一般理论中，我们知道，如果线性映射 $F, G$ 的组合 $F \circ G$ 是可能的，那么

$Ker(G) \subset Ker(F \circ G);$

在我们的上下文中，这给出了相应核之间的关联关系：$Ker(S{m-1}) \subset Ker(S \circ S{m-1}) = Ker(S_m)$

也就是说，$W_{m-1} \subset W_m$。 从这个关系中，我们还可以看到 $S(Wm) \subset W{m-1}$，因为

$S_{m-1}(S(W_m)) = S_m(W_m) = 0$

因此，我们可以考虑 SS 对 $W_m$ 的限制，并将其视为自同态 $S: W_m \rightarrow W_m$。 线性映射的关联关系和维度定理产生

$dim(W_{m-1}) \leq dim(W_m) = dim(Ker(S)) + dim(S(Wm)) \leq 1 + dim(W{m-1})$

由于 $S_{m-1}$ 和 $S_m$ 具有不同的度数，因此它们不能在 ~FF~ 中具有相同的根，因此它们作为线性映射的核是不同的。 这意味着

$W_{m-1} \neq W_m \Longrightarrow dim(Wm) = 1 + dim(W{m-1})$

并且由于 $dim(W_1) = 1$，我们得出的结论是 $dim(W_m) = m$ 并且 SS 将 $Wm$ 映射到 $W{m-1}$ 上。

Cantor 的基定理

Cantor 贡献的支柱之一是他的论文中被称为“定理 1.1”的内容，他证明了某个集合是其代数闭包在 $F_p$ 上的基。 为了陈述该定理，我们需要进行以下观察。 固定你最喜欢的素数 pp，并考虑由 SS 以下列方式定义的 $u_j \in \tilde{F}$ 的集合：

$S(uj) = u{j-1}, uj \in W{j+1} - W_j$

那么

a. 每个正整数 mm 在以 pp 为基数时都有一个展开式：也就是说，存在一个非负整数 kk 和整数 $0 \leq m_i \leq p-1$，其中 $0 \leq i \leq k$，使得

$m = \sum_{i=0}^{k} m_i p^i \quad \text{with} \quad m_k \neq 0$

为了象征性地表示这一点，我们写为 $E(m) = [m_0 m_1 \cdots m_k]$，我们可以将这个指数向量视为 mm 通过一个“展开映射”的图像

b. 令 $\gamma_m$ 为 $[m]_p$ 中的第一个非零条目。

c. 设置 $y_0 = 1$，对于正 mm，定义

$y_m = u^{E(m)} = u_0^{m_0} \cdot u_1^{m_1} \cdots u_k^{m_k}$

并观察到特别地

$y_{p^r} = u_r$

事实证明，集合 ${y_0, y_1, \dots}$ 具有_非常好的_性质，这些性质总结在以下定理中

定理（Cantor 的 1.11 定理）： 在与上述讨论相同的上下文中

1. ${y_0, y_1, \dots ym}$ 是 $W{m+1}$ 和 $ym \in W{m+1} - W_m$ 的一个基。

2. 当 $m \geq 1$ 时，则

$S(y_m) - \gammam y{m-1} \in W_{m-1}$

3. 完整集合 ${y_0, y_1, \dots}$ 是 $\tilde{F}$ 的一个基。

这个特定的基对于理论目的很重要，但也可以方便地考虑具有相对于 $S$ 的良好属性的 $W_m$ 的基； 我们已经遇到过一个这样的基，由 $u$ 定义的基。 设置

$U_m = {u_0, u1, \dots, u{m-1}}$

作为 $W_m$ 的一个基。 现在对于每个 $x \in W_m$，存在唯一的 $\alpha_i \in F_p$ 使得

$x = \sum_{i=0}^{m-1} \alpha_i u_i$

通过考虑 $0 \leq \alpha_i \leq p-1$，我们获得一个“替换映射”，该映射能够通过

$x \in Wm \longmapsto R(x) = \sum{i=0}^{m-1} \alpha_i p^i \in [0, p^m - 1]$

将 $x$ 解释为一个整数

持久的读者会注意到，此映射是先前出现的“展开映射”的逆映射。 这个特定基的一个好的性质是

$\alpha = R(x) \Longrightarrow \lfloor \alpha / p \rfloor = R(S(x))$

当描述 FFT 算法的时间到来时，这个事实将变得非常有用。

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