Additive FFT：背景

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

介绍

在本文中，我们将继续研究 二元域塔，其动机是 Diamond 和 Posen 提出的在 特征 2 的域上工作的完整协议 BINIUS。之前我们介绍了二元域塔中域元素的基本算术，即 Wiedemann 对 F2F2 的迭代二次扩展。我们着手解决在此类域中评估和插值多项式的问题，并考虑密码学应用。设计一种智能高效的算法来进行多项式求值将为在特征 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))O(nlog⁡(n))。显然，这一定是数学史上最被记录的事实之一；文献比比皆是。

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

正特征扩展塔的通用框架

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

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

L(x)=d∑i=0aixqiL(x)=∑i=0daixqi

其中 ai∈Fqai∈Fq （在本次讨论中，假设 pp 是素数，并且 q=pnq=pn 对于某个自然数 nn）。这些多项式的主要性质是，由于我们正在模 pp 运算，其行为就像线性代数意义上的线性变换一样。 也就是说，对于任何 u,v∈Fqnu,v∈Fqn 和 c∈Fqc∈Fq，它们都满足：

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

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

Ker(L)={v∈Fqn:L(v)=0}⊂FqnKer(L)={v∈Fqn:L(v)=0}⊂Fqn

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

素特征的扩展塔

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

S(t)=tp−tS(t)=tp−t

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

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

Sm(t)=S∘S⋯∘S(t)=S(Sm−1(t))Sm(t)=S∘S⋯∘S(t)=S(Sm−1(t))

• 为了便于表示，设置 W1=Ker(S)=FpW1=Ker(S)=Fp 和 Wm=Ker(Sm)Wm=Ker(Sm)：SmSm 的根的集合
• 这是所有机制开始运作的地方，因为对于所有 mm，以下各项都为真：

1. Wm−1⊂WmWm−1⊂Wm
2. S:Wm→Wm−1S:Wm→Wm−1 是一个满射函数
3. Wm−1Wm−1 在 WmWm 中具有 余维 1

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

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

Spk(t)=tppk−tSpk(t)=tppk−t

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

W0⊂Wp⊂Wp2⊂…Wpk⊂…W0⊂Wp⊂Wp2⊂…Wpk⊂…

在每一步中，我们都有 pp 次域扩展 [Wpk:Wpk−1]=p[Wpk:Wpk−1]=p。 映射 S:Wpk→Wpk−1S:Wpk→Wpk−1 的满射性意味着对于每个 k≥1k≥1 和每个 uk−1∈Wpk−1uk−1∈Wpk−1，始终存在一个元素 uk∈Wpk−Wpk−1uk∈Wpk−Wpk−1 使得

S(uk)=uk−1S(uk)=uk−1

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

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

W0⊂W2⊂W22⊂…W22k⊂…W0⊂W2⊂W22⊂…W22k⊂…

我们通过承认符号 W22k=TkW22k=Tk 的等价性来识别它。

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

• 塔的第一个生成元设置为 1。
• 第二个生成元是满足 S(u0)=1S(u0)=1 的元素 u0u0。 请注意，这等效于 u0u0 是 X2+X+1X2+X+1 的根。 很容易检查，由于该多项式在 F2F2 中没有根，因此 u0∉F2u0∉F2。
• 然后将第三个生成元定义为 S(u1)=u0S(u1)=u0。 这意味着 u21+u1=u0u12+u1=u0 或等效地 u21+u1+u0=0u12+u1+u0=0。 同样，这意味着 u1u1 是 X2+X+u0∈T1[X]X2+X+u0∈T1[X] 的根。 很容易检查，该多项式在 T1T1 中没有根，因此 u1∉T1u1∉T1。
• 对于 k>1k>1，其余元素由递归关系 S(uk)=uk−1S(uk)=uk−1 定义，并且也由一个域论关系 u2k+uk+uk−1=0uk2+uk+uk−1=0 定义。

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

m=mk2k+mk−12k−1+⋯+m020m=mk2k+mk−12k−1+⋯+m020

其中 mi∈{0,1}mi∈{0,1} 是 mm 的位，则：

ym=um00um11⋯umkk.ym=u0m0u1m1⋯ukmk.

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

• 基元素示例：

1. y0=1y0=1（对于 m=0m=0，所有 mi=0mi=0）

2. y1=u0y1=u0（对于 m=1m=1，二进制为 1212，因此 m0=1m0=1）

3. y2=u1y2=u1（对于 m=2m=2，二进制为 102102，因此 m1=1m1=1）

4. y3=u0u1y3=u0u1（对于 m=3m=3，二进制为 112112，因此 m0=1,m1=1m0=1,m1=1）

5. y4=u2y4=u2（对于 m=4m=4，二进制为 10021002，因此 m2=1m2=1）

6. 通常，y2r=ury2r=ur 对于 r=0,1,2,…r=0,1,2,…

TkTk 的这个显式基直接对应于 Diamond 和 Posen 所说的 Wiedemann 塔 TιTι 的“多线性基”。 他们声明，对于 TιTι，单项式集合 1,X0,X1,X0⋅X1,…,X0⋅…Xι−11,X0,X1,X0⋅X1,…,X0⋅…Xι−1 构成一个基，其中他们的 XiXi 有效地充当 Cantor 的 uiui。 重要的是要注意，Diamond 论文中的 Wiedemann 塔生成元使用略有不同的关系：X2j+1+Xj+1Xj+12+Xj+1Xj+1=0

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

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

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

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

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

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

Wm=⟨u⟩⊕Wm−1Wm=⟨u⟩⊕Wm−1

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

Wm=⋃α∈Fp(α⋅u+Wm−1)Wm=⋃α∈Fp(α⋅u+Wm−1)

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

α⋅u+Wm−1=Wαm−1α⋅u+Wm−1=Wm−1α

并观察到该集合恰好有 pm−1pm−1 个元素，因为 Wm−1Wm−1 是 Sm−1(t)Sm−1(t) 的根的集合，其度数为 pm−1pm−1。

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

2. 为了掌握其中一个 cαcα，以下观察结果派上用场：

   a. Wm−1Wm−1 是 pm−1pm−1 次多项式 Sm−1(t)Sm−1(t) 的根的集合

   b. 该多项式的平移将消失在 Wαm−1Wm−1α 上：

   Sαm−1(t)=Sm−1(t−α⋅u)Sm−1α(t)=Sm−1(t−α⋅u)

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

   c. 因此，代数基本定理指出 aa 除以 Sαm−1Sm−1α 的商的余数是一个度数严格小于 pmpm 的多项式，并且

   a(t)=Q(t)sαm−1(t)+bα(t)a(t)=Q(t)sm−1α(t)+bα(t)

   成立。 特别是，每当 w∈Wαm−1w∈Wm−1α 时，

   a(w)=Q(w)⋅0+bα(w)a(w)=Q(w)⋅0+bα(w)

   这意味着在 Wαm−1Wm−1α 上 a≡bαa≡bα。

3. 然后，该算法递归调用自身，以评估其对应的较小子空间 Wαm−1Wm−1α 上的每个 bα(t)bα(t)。

   • 基本情况：

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

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

逆过程：插值

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

计算成本和效率

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

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

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

为了评估 WmWm 所有点上的度数 <n=pm<n=pm 的多项式：

1. A 运算的总数约为 O(n(logn)1+logp((p+1)/2))O(n(log⁡n)1+logp⁡((p+1)/2))。 对于 p=2p=2，这简化为大约 O(n(logn)1.585)O(n(log⁡n)1.585)。

2. M 运算的总数约为 O(nlogn)O(nlog⁡n)。

总结

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

附录 - 证明和想法

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

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

L(x)=d∑i=0aixqiL(x)=∑i=0daixqi

其中 ai∈Fqai∈Fq

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

- 它们是线性变换： 如果 L(x)L(x) 是一个系数在 FqFq 中的线性化多项式，则从 FqnFqn 到自身的映射 x↦L(x)x↦L(x) 是一个线性变换，考虑到这个扩展是 FqFq 上的 n 维向量空间。 这意味着对于任何 u,v∈Fqnu,v∈Fqn 和 c∈Fqc∈Fq：

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

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

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

Ker(L)={v∈Fqn:L(v)=0}⊂FqnKer(L)={v∈Fqn:L(v)=0}⊂Fqn

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

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

  M(X)=L∘N(X)M(X)=L∘N(X)

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

Sm(t)=S∘S⋯∘S(t)=S(Sm−1(t))Sm(t)=S∘S⋯∘S(t)=S(Sm−1(t))

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

Ker(G)⊂Ker(F∘G);Ker(G)⊂Ker(F∘G);

在我们的上下文中，这给出了相应核之间的关联关系：Ker(Sm−1)⊂Ker(S∘Sm−1)=Ker(Sm)Ker(Sm−1)⊂Ker(S∘Sm−1)=Ker(Sm)

也就是说，Wm−1⊂WmWm−1⊂Wm。 从这个关系中，我们还可以看到 S(Wm)⊂Wm−1S(Wm)⊂Wm−1，因为

Sm−1(S(Wm))=Sm(Wm)=0Sm−1(S(Wm))=Sm(Wm)=0

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

dim(Wm−1)≤dim(Wm)=dim(Ker(S))+dim(S(Wm))≤1+dim(Wm−1)dim⁡(Wm−1)≤dim⁡(Wm)=dim⁡(Ker(S))+dim⁡(S(Wm))≤1+dim⁡(Wm−1)

由于 Sm−1Sm−1 和 SmSm 具有不同的度数，因此它们不能在 ~FF~ 中具有相同的根，因此它们作为线性映射的核是不同的。 这意味着

Wm−1≠Wm⟹dim(Wm)=1+dim(Wm−1)Wm−1≠Wm⟹dim⁡(Wm)=1+dim⁡(Wm−1)

并且由于 dim(W1)=1dim⁡(W1)=1，我们得出的结论是 dim(Wm)=mdim⁡(Wm)=m 并且 SS 将 WmWm 映射到 Wm−1Wm−1 上。

Cantor 的基定理

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

S(uj)=uj−1,uj∈Wj+1−WjS(uj)=uj−1,uj∈Wj+1−Wj

那么

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

m=k∑i=0mipiwith mk≠0m=∑i=0kmipiwith mk≠0

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

b. 令 γmγm 为 [m]p[m]p 中的第一个非零条目。

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

ym=uE(m)=um00⋅um11⋅umkkym=uE(m)=u0m0⋅u1m1⋅ukmk

并观察到特别地

ypr=urypr=ur

事实证明，集合 {y0,y1,…}{y0,y1,…} 具有_非常好的_性质，这些性质总结在以下定理中

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

1. {y0,y1,…ym}{y0,y1,…ym} 是 Wm+1Wm+1 和 ym∈Wm+1−Wmym∈Wm+1−Wm 的一个基。

2. 当 m≥1m≥1 时，则

S(ym)−γmym−1∈Wm−1S(ym)−γmym−1∈Wm−1

3. 完整集合 {y0,y1,…}{y0,y1,…} 是 ~FF~ 的一个基。

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

Um={u0,u1,…,um−1}Um={u0,u1,…,um−1}

作为 WmWm 的一个基。 现在对于每个 x∈Wmx∈Wm，存在唯一的 αi∈Fpαi∈Fp 使得

x=m−1∑i=0αiuix=∑i=0m−1αiui

通过考虑 0≤αi≤p−10≤αi≤p−1，我们获得一个“替换映射”，该映射能够通过

x∈Wm⟼R(x)=m−1∑i=0αipi∈[0,pm−1]x∈Wm⟼R(x)=∑i=0m−1αipi∈[0,pm−1]

将 xx 解释为一个整数

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

α=R(x)⟹⌊α/p⌋=R(S(x))α=R(x)⟹⌊α/p⌋=R(S(x))

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

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