FFT/NTT/MTT 的大整数乘法

• 系数表示与点值表示
• 单位根的性质
• 分治蝶形运算

FFT 的核心是用点值表示替代系数表示：一个 n-1 次多项式（共 n 个系数）由 n 个点值唯一确定，且点值相乘即可得到卷积的多项式点值。FFT 在 n 个单位根 ω=exp(2πi/n) 处对多项式求值，利用单位根的性质 ω^{k+n/2} = -ω^k 和 ω_k = ω_{2k}^2 实现分治：把多项式按奇偶拆成两个系数子多项式，递归求值，使得每个点值只需 O(log n) 层、每层 O(n) 次蝶形运算，总复杂度 O(n log n)。逆变换（IDFT）用共轭单位根再除以 n 即可还原系数。

"点值相乘"这一步把卷积的 O(n^2) 降为 O(n)，求值与插值各用分治 O(n log n)，三者合计 O(n log n) 完成卷积。

• Karatsuba 分治
• 三次乘法替代四次
• 工程阈值

Karatsuba 把 n 位数 x = x1·B^m + x0、y = y1·B^m + y0 拆成高低两半。朴素需要 4 次半长乘法，Karatsuba 用 x1·y1、x0·y0、(x1+x0)(y1+y0) 三次乘法，再由 (x1+x0)(y1+y0) - x1·y1 - x0·y0 得到交叉项 x1·y0+x0·y1。递推复杂度 T(n) = 3T(n/2) + O(n) = O(n^{log_2 3}) = O(n^1.585)。工程上，n 很小（如 < 几十位）时用朴素乘法；中等规模用 Karatsuba/Toom-3；很大规模用 FFT。阈值通常通过实测确定，如 GMP 在乘数约 32-64 个 limb 时切换。

Karatsuba 通过"加法换乘法"减少乘法次数，是分治乘法的经典；工程库按规模分档切换算法。

• 卷积定义
• 多项式乘法与卷积
• FFT 三次变换

卷积定义：c_k = Σ_{i+j=k} a_i·b_j。两个多项式相乘的系数恰好就是卷积，因此多项式乘法是卷积。暴力计算需要对每个 k 枚举 i、j，复杂度 O(n^2)。FFT 用三次 O(n log n) 变换替代：① 正变换把 a 和 b 分别求值为点值（两次 O(n log n)）；② 点值逐项相乘（O(n)）；③ 逆变换插值回系数（一次 O(n log n)）。总共 3 次 O(n log n) 变换，把 O(n^2) 降到 O(n log n)。

卷积是"加法定标"的求和，FFT 利用点值表示下相乘的独立性，把卷积变成点值逐项乘，是加速的根源。

• Schönhage-Strassen 原理
• GNU MP 中的实现
• Boost.Multiprecision 中的实现

Schönhage-Strassen（S-S）用负循环卷积与费马数模实现大整数乘法，复杂度 O(n log n log log n)，是已知渐近最优的整数乘法之一。在 GNU MP 中，当乘数位数极大（通常达到百万位量级）时，mpz_mul 会切换到 S-S 实现；Boost.Multiprecision 的 cpp_int 在极端大数（如数亿位）上也支持 S-S。两者的工程设计都是把 S-S 作为 FFT 之上的最高层，用于超大规模乘法，而中小规模用 Karatsuba/Toom/FFT。

S-S 理论上渐近最优，但常数因子大，工程上只在超大数时启用，体现了"理论最优 vs 实际常数"的权衡。

• IDFT 归一化
• 位逆序重排
• 迭代实现

正变换 DFT 用 n 次单位根 ω，逆变换 IDFT 用共轭单位根 ω^{-1}，两者互逆。由于 DFT 矩阵的逆是 DFT 矩阵的共轭转置除以 n，所以 IDFT 后每个系数需除以 n 才能还原。若直接按定义递归实现，输出的顺序是位逆序（bit-reversal）的；迭代实现（in-place）先把输入重排为位逆序，再逐层蝶形合并，这样输出就是自然顺序。位逆序重排保证迭代 FFT 的正确性。

"除以 n"是 DFT/IDFT 互逆的归一化因子；位逆序重排是迭代 FFT 的索引约定，两者都是 FFT 实现的关键细节。

• 费马数模 2^n+1
• 循环卷积
• 负循环卷积防溢出

Schönhage-Strassen 用费马数模 2^n+1 做循环卷积，因为 2 在模 2^n+1 下是 2n 次单位根，且乘法可快速用移位（×2 左移一位）完成，无需昂贵乘法。用 NTT 模 2^n+1 做卷积时，若结果系数超过模数会溢出，S-S 采用负循环卷积：把系数按符号交替折叠（负系数），使结果长度减半，避免溢出，代价是编码时需处理符号。负循环卷积保证结果系数都在模数范围内。

费马数模 + 负循环卷积是 S-S 的核心技巧：用移位替代乘法、用负循环减半规避溢出，使卷积在超大整数上仍高效。

• Toom-3 分治
• 复杂度层级
• 适用规模

Toom-3（Toom-Cook）把数拆成 3 段，用 5 个点值（在 5 个位置求值）相乘，再用插值还原，递推 T(n) = 5T(n/3) + O(n) = O(n^{log_3 5}) = O(n^1.465)。它介于 Karatsuba（O(n^1.585)，拆 2 段、3 次乘法）和 FFT（O(n log n)）之间。通用地，Toom-k 拆 k 段、2k-1 次乘法，复杂度 O(n^{log_k(2k-1)})，随 k 增大趋近 O(n)。工程上 Toom-3 用于中等规模（Karatsuba 之上、FFT 之下）。

Toom-Cook 是 Karatsuba 的推广（Karatsuba 即 Toom-2），通过"更多段数 + 更多但对数更少的乘法"逐步逼近 FFT 的渐近复杂度。

• 浮点误差来源
• 精度与性能取舍
• 工程处理

直接用浮点 FFT 做大整数乘法，误差随位长和变换规模累积，结果可能不精确，需要额外的舍入与校正。S-S 采用整数环上的 NTT（模 2^n+1 或 NTT 友好素数），完全避免浮点误差，以换取更多运算。工程取舍：浮点 FFT 更快但精度受限，适合中等规模；整数 NTT/S-S 无误差但更慢，适合超大规模。库（如 FFTW、GMP）视规模选择：浮点画布 + 误差界分析，或整数精确卷积。

浮点误差决定"能否直接用 FFT"，位长与变换规模决定误差累积，工程需在速度与精度间权衡。

• MTT 原理
• 多模数 NTT
• CRT 还原

MTT 用多个 NTT 友好素数模数分别做 NTT 卷积，得到每个模下的卷积结果，再用中国剩余定理（CRT）把各模结果还原为真实整数系数。因为每个模数较小，结果系数可能超过单个模数，用多个模数（通常 2-3 个）的乘积覆盖真实系数范围，CRT 合并后得到精确结果。这避免了浮点误差，只需多次 NTT 与 CRT 求解。

MTT 的取舍是"以多次 NTT 换精度"：比单模 NTT 更精确（可还原任意模数结果），比浮点 FFT 更慢但无误差。

• 浮点精度问题
• 位长与误差
• 拆分降低误差

浮点 FFT 中，每个蝶形运算的舍入误差随层数累积，总误差与变换规模及位长相关。位长越大，系数越大，浮点相对误差导致低位不可靠，直接 FFT 会出错。降低误差的方法是把大整数拆成多个小段（如按 2^15 或 2^31 拆分），用多个 FFT 变换（如三次变换）分别处理高位/低位，再合并，避免单次 FFT 中系数过大。这牺牲了部分速度换取精度。

"拆分 + 多次变换"是浮点 FFT 做精确大整数乘法的常用降误差手段，让系数在浮点可表示范围内。

• NTT 友好素数
• 原根
• 单位根对应

NTT 用整数模素数 p 替代浮点单位根，需要 p 含大 2 的幂因子，使 p-1 能被变换长度 n 整除，即 n | p-1。998244353 = 119·2^23 + 1，含 2^23 因子，支持长度达 2^23 的 NTT。其原根 g = 3。NTT 中 g^{(p-1)/n} 相当于 FFT 中的 n 次单位根 ω，即 ω = g^{(p-1)/n} mod p，具有与复数单位根相同的循环性质 ω^n = 1。原根保证生成的子群是循环群，长度恰为 n。

NTT 友好素数的条件是 p-1 含足够大的 2 的幂；原根 g 的幂次生成全部单位根，与 FFT 的 ω 对应。

• 卷积的泛化
• 字符串匹配转卷积
• 生成函数计数

这些问题的共同数学结构是卷积。字符串匹配：把模式串和文本串编码成 0/1 向量，匹配位置可化为卷积的相关系数（带通配符时用二值编码组合），卷积峰值指示匹配位置。多项式乘法与高精度乘法本身就是卷积（系数即数字）。生成函数计数：把组合对象编码为生成函数，系数即为计数，两个生成函数相乘即卷积，得到组合计数。统一用 NTT/FFT 的 O(n log n) 卷积加速。

卷积是"按指标求和"的抽象，把离散匹配、乘法、计数都归一到同一数组运算，从而复用 FFT/NTT 加速。

• 系数表示
• 点值乘法
• 逆变换与进位

流程：① 把两个大整数按位拆成系数数组（若干进制分量）；② 正变换 FFT 把两个系数数组分别转为点值表示（O(n log n)）；③ 点值逐项相乘得到乘积的点值表示（O(n)）；④ 逆变换 IDFT 还原乘积的系数（O(n log n)）；⑤ 系数归一化（除以 n）后处理进位（从低位向高位进位），得到最终结果。整个流程把高精度乘法的 O(n^2) 降为 O(n log n)。

高精度乘法 = 多项式乘法 = 卷积，FFT 的"求值-相乘-插值"三步恰好对应"点值-乘点-还原系数"。

• in-place 迭代
• 蝶形运算
• 位逆序重排

迭代 in-place FFT 分两步：先做位逆序重排（把输入按比特反转的索引重排），再逐层做蝶形合并。每层长度 len 从 1 翻倍到 n，对每个块做蝶形：w = a[k]，t = a[k+len/2]·ω，则 a[k] = w + t，a[k+len/2] = w - t。in-place 只需一个数组，每层 O(n) 次蝶形，总 O(n log n)。

位逆序重排 + 循环层合并是迭代 FFT 的标准写法，避免递归栈，in-place 省内存。

• invNTT 原根逆元
• 除以 n
• 与 FFT 对称

NTT 正变换用原根 g 的幂 w = g^{(p-1)/n} 作为单位根；逆变换 invNTT 用 w 的逆元 w^{-1}（即 g 的逆元的幂），使前向与逆向相互抵消。同样，由于 DFT 矩阵逆含 1/n 因子，invNTT 最后需把每个系数乘以 n 的逆元（即 mod p 下除以 n）。这与 FFT 中"IDFT 用共轭单位根并除以 n"完全对称，只是 NTT 在整数环上做、用逆元替代共轭。

正逆变换的对称性（用 w 与 w^{-1}、补 1/n）是 NTT 与 FFT 共有的结构，保证变换与逆变换互逆。

• GHK 算法
• 拆分系数
• 任意模数卷积

GHK（Garbow-Hilgemick-Knuth）用于任意模数下的卷积，思路是把每个系数拆成高低位（如 a = a_hi·B + a_lo，B 取 √p 量级），将原卷积分解为若干小模数卷积，再组合。这样避免了个别系数过大导致溢出，用浮点 FFT 也能得到精确结果。它等价于"拆分 + 多次 FFT + 组合"，是任意模数卷积的工程实现。

GHK 通过对系数拆分控制量级，使浮点 FFT 的误差在可接受范围，从而支持任意模数，是 MTT 之外的常用方案。

• 两个模数 NTT
• CRT 还原
• 精确性 vs 速度

MTT 用两个 NTT 友好素数模数 p1、p2 分别做 NTT 卷积，得到结果在模 p1、p2 下的值。由于真实系数范围小于 p1·p2（两模数乘积），用 CRT 可从两个模结果唯一还原真实整数系数。相比浮点 FFT，MTT 全程整数运算，无浮点误差，因此更精确；但因为要做多次 NTT（正逆变换各 2 次以上）和 CRT 求解，运算量更大，所以更慢。

"多模数 + CRT"是"用多次变换换精度"，现代实现用 3 个模数（如 998244353、1004535809、469762049）以平衡精度与速度。

• NTT 友好素数
• 模数限制
• 普通模数绕过

NTT 需要模数 p 满足 p-1 含足够大的 2 的幂（n | p-1），使存在 n 次单位根，这类素数称 NTT 友好素数。若用普通模数，则无法直接做 NTT。绕过方法：① 用 MTT（多个 NTT 友好素数分别做 NTT + CRT 还原到普通模数）；② 用 GHK 拆分法；③ 用浮点 FFT 后取模。这些方法把"单次 NTT"扩展为"多模数 + CRT"或"拆分卷积"，从而处理任意模数。

NTT 友好素数提供完整的单位根结构，普通模数缺该结构，必须借助多模数 CRT 或拆分规避。

• 卷积与多项式乘法
• 点值相乘
• 逆变换流程

两个多项式相乘的系数序列就是它们系数序列的卷积，因此多项式乘法 = 卷积。完整流程：① 把两个多项式系数数组扩展到长度 ≥ 2n-1，并补零到 2 的幂；② 对两个数组分别做正变换（FFT/NTT）得到点值表示；③ 点值逐项相乘（对应位置相乘）；④ 对乘积数组做逆变换（IDFT/invNTT）还原系数；⑤ 归一化（除以 n）并处理进位/取模，得到最终多项式系数。这一步恰好实现了卷积。

"点值相乘 + 逆变换"是卷积的定义式在变换域的高效实现，FFT 的引入使卷积从 O(n^2) 变 O(n log n)。

• 朴素 vs FFT 常数
• 阈值切换
• 工程库实现

朴素 O(n^2) 乘法虽然渐近差，但常数因子极小（无变换、无递归、无复数）；FFT/NTT 有常数因子（复数运算、位逆序、多次变换、浮点误差处理），n 小时 FFT 的固定开销超过朴素。因此工程库用阈值切换：n 小于某阈值（如几十到几百）用朴素，之上用 Karatsuba/Toom，更大用 FFT/NTT。阈值通过实测确定（如 GMP 在乘法规模约 32-64 limb 切 Karatsuba，更大切 FFT）。

渐近复杂度映射到实际性能需考虑常数，阈值切换是"理论最优"与"实际常数"相结合的工程实践。