加法 FFT

原创 Kurt Pan XPTY

2025年07月01日 13:39

原文：https://blog.lambdaclass.com/additive-fft-background/
作者：LambdaClass
译者：Kurt Pan

引言

在本文中，我们继续研究二进制域塔，灵感来源于 Diamond 和 Posen 为在特征 2 域上运行的完整协议 BINIUS（https://www.binius.xyz）所提出的方案。此前我们已经介绍了在二进制域塔中域元素的基本算术，即 Wiedemann 对的迭代二次扩张。我们着眼于在此类域上对多项式进行求值与插值的问题，并考虑其在密码学中的应用。设计一个漂亮且高效的多项式求值算法，将为在特征 2 下高效实现 Reed–Solomon 编码铺平道路，而 Reed–Solomon 编码是多项式承诺的关键模块。

关于多项式乘法的一般问题

既然我们已经了解了 Wiedemann 二进制域塔的结构，自然而然要思考如何在该塔上对函数进行求值或相乘。对我们的目标而言，这点很重要，因为在一个精心选定的基域子集（例如次单位根）上对多项式求值，正是使用 Reed–Solomon 技术进行消息编码的基础；从这个角度看，多项式求值问题与 Reed–Solomon 编码问题几乎等价。

回想一种高效的多项式乘法方法：快速傅里叶变换（FFT）。它采用著名的流程

对于熟悉这些概念的读者来说，用更专业的术语来说，“多项式求值”代表“对多项式进行快速傅里叶变换 (FFT)”，逐点乘表示“逐点相乘它们的快速傅里叶变换”，而插值则表示“对结果进行逆快速傅里叶变换”。这种通用方案使我们能够绕过高中时将两个多项式相乘并应用分配律的计算成本。这些“求值”和“插值”步骤通常涉及矩阵乘法；每当我们求多项式的幂时，如果其本原次方根为单位根，且是的幂，则可以使用递归算法，并且所有这些都可以快速完成，例如。显然，这必须是数学史上记录最多的事实之一；文献中对此进行了大量的论述。

那么，能否在此处应用 FFT 呢？问题在于，在有限域中“单位根”可能并不存在，或者要找到足够多的单位根就必须在更大、更复杂的扩域中运行。这一基本限制使得经典 FFT 在这类域上要么不可行，要么效率极低。

正特征扩域塔的一般框架

为克服此难题，我们审视 David Cantor 于 1989 年发表的论文《On Arithmetical Algorithms over Finite Fields》。他在其中提出了一种类似 FFT 的算法，但它作用于基域的加法子群而非乘法子群；由于此时我们处理的是群元素的加法，而非乘法，这一方案通常被称为 加法 FFT。Cantor 构造了“单位根”的加法对应物，并像经典 FFT 那样将问题递归地拆解为更小的子问题。好消息是，这些加法子群正是一系列向量子空间，与 Wiedemann 的工作及 Diamond 和 Posen 的方案中出现的熟悉子域密切相关。

构建加法 FFT 的关键对象是 线性化多项式；它是一类特殊多项式，由于其对基域中加法和数乘的“线性”特性，展现出极其有趣的性质。*线性化多项式的所有单项式次数均为的幂，即 *；其一般形式为（更多细节请参见文末附录）：

其中（假设为素数，）。这些多项式的主要性质在于：由于我们在模意义下运算，它们表现得就像标准线性代数意义下的线性变换——对任意和，都有

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

该事实源自线性代数理论；它意味着任意根的线性组合仍是的根。最后，线性化多项式的一个绝佳性质是：它们的复合仍为线性化多项式。这正是 Cantor 关于正特征扩域塔描述的基石。

素特征扩域塔

为了简明起见，我们聚焦一个简单但重要的例子：固定素数，令为的代数闭包（例如是的代数闭包），取线性化多项式

从上述基本定义出发，我们得到如下对象：

考虑将与自身依次复合，得到一族线性化多项式
记，，即的根集合。
这是所有钟表装置开始运转的地方，对所有，以下三点成立：

是满射
在中的余维数（codimension）为 1

https://en.wikipedia.org/wiki/Codimension

最后一点在Cantor思想的结构中扮演着非常重要的角色：这意味着，如果我们把想象成一块巧克力棒，那么它也可以被认为是恰好个不相交的副本的并集：画一个矩形，称之为，然后把它分成个形状和大小相同的部分。每一个都是的副本！

掌握了这个（非常）简短的总结后，接下来就是好东西了。一个关键的观察是，每当时，由于我们以为模，因此所涉及的线性化多项式具有非常整齐的形状：

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

其中每一步我们都有度为的域扩张。映射的满射性意味着对于每个和每个，总存在一个元素使得

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

令，即可重现 Wiedemann 的二进制域塔：

并认出记号等价关系

此外，映射的满射性还让我们能够为塔中每一层构造生成元与基。具体而言：

第一层生成元取为 .
第二层生成元为满足
的元素，即为的根，由于该多项式在上无根，故。
第三层生成元定义为满足
这蕴含着，或者等价地。同样，这蕴含着是的根。很容易验证这个多项式在中没有根，因此在中也没有根。
对于，则递归令
并满足域论关系。

基于这些生成元，Cantor 按照的二进制展开定义基元素：这模仿了Wiedemann 二进制塔中元素域乘法的自然运用。具体来说，如果我们写下的二进制展开式

则

举例说明：

（时所有）
（时二进制，故）
（时二进制，故）
（时二进制）
（时二进制）
一般地，。

对于的显式基，直接对应于 Diamond 和 Posen 所称的 Wiedemann 塔的多线性基。他们指出，对于，单项式集

构成一个基，其中的实际上就是Cantor的。值得注意的是，Diamond 论文中的Wiedemann 塔生成元使用了一个略有不同的关系：

尽管在特定的生成关系中存在这些差异，但这些迭代二次扩张的底层代数结构与Cantor的有效基表示和算术的一般框架是一致的。

加法 FFT 的递归“分治”策略：多项式求值

Cantor的加法 FFT 的核心机制是一个递归的＂分治＂过程，这与传统 FFT 算法的效率原则如出一辙。这里，我们将首先概述一下求系数为的次数为的多项式的问题。下文中，我们将保留前几节中使用的符号。

设定求值域：子空间

目标是在的个元素上求的值，此处类似于经典 FFT 中的阶单位根。
至关重要的是，可以划分为个较小的、不相交的＂陪集＂。这样就可以对问题进行分层分解，就像在经典情况中是 2 的幂的情况一样。更具体地说，我们知道是一个线性映射，它将射到上，并且该像的余维数为 1 。这确保存在一个元素使得

因为恰好有个元素，所以

并观察到该集合恰好有个元素，因为是的根集，其阶为。

递归步骤：分解问题

现在，为了求出在上的值，只要知道在每一个陪集上的值就足够了。由于这些陪集有个元素，如果我们能把这个问题简化为求出一个次数严格小于 的多项式在上的值（理想情况下是），那就太棒了。
为了获得这样的，以下观察结果很有用： a．是次多项式的根集

b．该多项式的一个平移将在处消失：

不相信请自己检查一下。

c．代数学基本定理指出，除以的商的余数是次数严格小的多项式，且

成立。特别地，当时，

这意味着在上。

然后，该算法递归调用自身来对其对应的较小子空间的每个求值。

基例：

这种递归分解一直持续到多项式达到0次，即变成常数。
这些得到的常数是所要的原始多项式在中的点处的函数值

逆过程：插值

Cantor 还概述了逆运算，即插值。如果已知多项式在内所有点的值，则可以反转加法 FFT 算法的步骤来重构原始多项式的系数。此逆过程涉及类似的除法和加法求和技巧，但执行顺序相反。

计算开销与效率

Cantor 严格分析了他的算法的计算复杂性，将操作分为两类：

A-操作（加法类）： 计算开销对应基域中的加法。
M-操作（乘法类）： 计算开销对应基域中的乘法。

在的所有点处计算次数为的多项式：

A 操作的次数约为。对于，可简化为大约。
M 操作总次数约为。

总结

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

附录 —— 证明与思路

这里我们总结了文中提到的线性多项式的大部分证明、定义和技术细节。我们从最初的定义开始，推导了一些所使用的性质。

定义（线性化多项式）
在有限域上的线性化多项式具有如下形式：

这里我们将它们的一些主要性质收集起来并列成一个列表；其中大多数都是容易证明的事实，可以作为鼓励性的练习（同时也提醒我们基础线性代数的重要性）：

它们是线性变换：如果是一个系数在上的线性化多项式，则映射是一个从到其自身的线性变换，将该扩张视为上的维向量空间。这意味着对于任意和都有：
（该性质源于将具有个元素的域表征为多项式的分裂域。）由于是线性映射，因此它的根集构成一个向量空间：

复合的神奇效应：通常，多项式的复合只会产生一个新多项式，而在一般情形下难以进一步描述。但由于线性化多项式可被视为线性映射，其复合带来以下惊人后果：

从定义出发，线性化多项式可看作是在普通多项式前复合了。也就是说，存在一种对应关系，将上的线性化多项式关联到“-常规”多项式，二者在系数和结构上保持一致。
由于定义和线性性质，两个线性化多项式的复合仍为线性化多项式。该二元操作不满足交换律，但对多项式加法满足分配律。
若将复合作为一种非交换乘法来理解，则可引入类似除法的概念：若存在线性化多项式使得
则称 符号上除。
更重要的是，线性化多项式的符号可除性与其 -常规对应之间存在一一对应：符号上除当且仅当在普通意义下除。
线性化多项式在组合意义下不可约当且仅当其 -常规对应在上不可约。需要注意的是，组合意义下不可约的线性化多项式在普通意义下总是可约的（它至少含因子）。

关于扩域塔的构造：将线性化多项式  与自身依次复合
会产生算法所作用的子集。根据线性映射的一般理论，若线性映射  可复合，则有
在本情形下，这意味着对应的核之间满足
即。又因
可知。将  限制到，视为  的自同态；由核-像维数定理及上述包含关系得
由于  与  次数不同，其在  中的根集也不同，故对应核异。由此可推得
又，由归纳可得，且  将  满射至。