FFT（快速傅里叶变换）和 NTT（快速数论变换）

Table of Contents

要理解 FFT（快速傅里叶变换）和 NTT（快速数论变换），首先必须理解它们试图解决的核心问题：多项式乘法（Polynomial Multiplication），或者更广泛地说，卷积（Convolution）。

1. 理论基础：多项式的两种表示法

在数学中，一个 次多项式 有两种等价的表示方式。理解这两种表示法的转换是 FFT/NTT 的灵魂。

A. 系数表示法 (Coefficient Representation)

这是最直观的表示法，即用一个系数向量来表示多项式：

问题： 在这种表示法下，两个多项式 和 相乘得到 ，其系数 是通过卷积计算的：。

计算复杂度： 计算所有系数需要两两相乘，复杂度为 。当 很大时，这太慢了。

B. 点值表示法 (Point-Value Representation)

根据代数基本定理，一个 次多项式可以被 个不同的点唯一确定。如果我们选定 个不同的 值 ，并计算出对应的 ，那么集合 也可以唯一表示这个多项式。

优势： 在这种表示法下，多项式乘法变得异常简单。如果 和 在同一点 的值分别是 和 ，那么乘积多项式 在 的值仅仅是 。

计算复杂度： 只需要进行 次标量乘法，复杂度为 。

2. 核心问题与解决方案

这就引出了 FFT/NTT 的核心逻辑链条：

  1. 目标： 快速计算多项式乘法。
  2. 障碍： 系数乘法 太慢；点值乘法 很快，但我们通常只知道系数。
  3. 策略：
    • 第一步（求值 Evaluation）：将系数表示法转换为点值表示法。
    • 第二步（点乘 Point-wise Multiplication）：在点值表示下进行 的乘法。
    • 第三步（插值 Interpolation）：将结果从点值表示法还原回系数表示法。

瓶颈： 普通的求值（代入 个点）和插值（拉格朗日插值或高斯消元）通常也需要 。

突破： FFT 和 NTT 的伟大之处在于，通过巧妙地选择那 个点（），利用分治法（Divide and Conquer），将求值和插值的过程加速到 。

3. FFT（快速傅里叶变换）：复平面上的分治

FFT 选择的特殊点是单位复根（Roots of Unity）。

这里的“巧妙选择”是什么？

为了使用分治法，选取的点集必须具有对称性和周期性。在复平面上，方程 的 个解正好构成了一个圆上的均匀分布点。这些解被称为 次单位根，记为 （其中 ）。

核心性质

  1. 折半引理（Halving Lemma）： 。这意味着 次单位根平方后，落入 次单位根的集合中。这是分治递归的基础。
  2. 消去引理： 。
  3. 周期性： 。这意味着我们在计算前半部分时，可以免费得到后半部分所需的信息。

FFT 算法步骤

我们要计算 。 假设 是 2 的幂（如果不是，补零凑整）。 将多项式 按系数下标的奇偶性拆分： 令 和 。 则有：

代入单位根 ： 利用折半引理 ：

结论： 原本规模为 的问题，被转化为了两个规模为 的子问题（求 和 在 次单位根上的值）。 这就是经典的递归结构：，解得 。

逆变换 (IFFT)

插值过程（从点值回系数）与正变换惊人地相似。只需要将 替换为 （共轭复数），最后将结果除以 即可。

4. NTT（快速数论变换）：从复数域到有限域

FFT 极其强大，但存在一个致命缺陷：精度丢失。 FFT 依赖复数和三角函数运算，计算机使用浮点数存储，经过大量运算后会产生误差。在数论、组合数学或大整数乘法题目中，我们需要精确的整数结果，浮点误差是不可接受的。

NTT 是 FFT 在模运算域（有限域）上的变体。它保留了 FFT 的分治结构，但将“单位复根”替换为“原根”。

理论迁移：寻找 的替代品

在 FFT 中， 的核心性质是 且 。 在模 的整数域中（ 通常为质数），我们需要找到一个整数 （原根），使得 的幂次在模 下也能形成类似的循环群结构。

若 是一个质数，且 （这种质数被称为 NTT 友好的质数，如 ），那么模 存在原根 。 我们可以定义模域下的“单位根” ：

这个 完美继承了 的所有性质：

  1. 归一性： 。
  2. 折半性： 。
  3. 互异性： 在模 下互不相同。

NTT 算法流程

流程与 FFT 完全一致，只是将复数运算换成了模 下的整数运算：

  1. 复数加法 模加法。
  2. 复数乘法 模乘法。
  3. 单位根 。

优势与局限

  • 优势： 没有任何精度损失，全是整数运算，且取模运算通常比浮点运算快。
  • 局限： 模数 必须具备特殊形式（），且多项式系数乘积的结果不能超过模数（或者是必须要对该模数取模的问题）。如果需要任意模数，则需要使用“任意模数 NTT”（通常涉及拆系数或多个模数合并 CRT）。

5. 总结

要掌握 FFT/NTT，请记住：

  1. 宏观视角： 这是一种“降维打击”。我们在时域（系数）上处理卷积很困难，于是通过变换穿越到频域（点值），在频域上乘法变得极其简单，处理完后再穿回来。
  2. 微观操作： 能够穿越的关键在于利用了数学对象的对称性（圆上的点、模域的循环群）。分治法利用这种对称性，避免了重复计算。
  3. 对比：
    • FFT： 也就是复平面上的圆。适用于信号处理、不需要绝对精度的科学计算。
    • NTT： 也就是模运算下的“圆”（循环群）。适用于大整数乘法、组合计数、加密算法等需要精确整数解的场景。

最终公式化记忆： 复杂度从 降至 。