多项式乘法算法

卷积公式的困难不是某个系数难算，而是所有系数共享大量乘积。分治算法寻找可复用的线性组合：Karatsuba 用一次“和的乘积”同时携带两个交叉块，Toom–Cook 把更多分块看成一个较低次数的外层多项式，变换算法则干脆选择一个乘法已经对角化的点值坐标系。算法越快，越依赖系数环允许做哪些加法、除法和单位根运算。

$M(N)$ 只约束环运算次数，本身不提供空间界。逐对累加的 schoolbook 实现保存 $m+n-1$ 个输出系数，另需 $O(1)$ 个系数累加槽位；按深度优先顺序复用子问题缓冲区的标准 Karatsuba，或采用长度 $O(N)$ 变换的 FFT 乘法，可使用 $O(N)$ 个系数工作槽位，递归控制信息和系数 bit 存储另计。

$M(N)$ 是代数运算模型中的接口，不等于 bit complexity。若系数是 $b$ bit 整数，一次系数乘法的成本随 $b$ 增长，输出系数的 bit 长度可达到约 $2b+\log N$；若系数是浮点数，逐次蝶形会累积舍入误差；若系数在 ${\mathbb{F}}_p$ 中，所需的 $2N$ 次单位根可能根本不存在。把“$O(N\log N)$ 个域运算”直接翻译成同样数量的机器指令，会漏掉这些决定实现的条件。

令 $A=1+2x+3x^2+4x^3$、$B=5+6x+7x^2+8x^3$，按 $s=2$ 分块：

三次子乘积为

以及 $P_{\mathrm{\Sigma }}=(4+6x)(12+14x)=48+128x+84x^2$。交叉块是 $P_1=P_{\mathrm{\Sigma }}-P_0-P_2=22+60x+40x^2$，故

这个四项例子只节省一次子乘法，递归到大规模后才形成指数差异。

FFT 路线有明确边界。长度补零不足会计算循环卷积；在 ${\mathbb{F}}_{17}$ 中存在阶 $16$ 的单位根，可做长度 $8$ 的数论变换，但在任意给定域中不能假定同样的根存在。复数 FFT 乘整数多项式时还要证明舍入后能唯一恢复精确系数。对极稀疏而指数巨大的输入，先建长度 $N$ 的向量可能已经不可行，项表乘法反而更合适。

快速除法也由乘法接口控制。把首一除数 $B$ 的系数反转为 $B^{\ast }$ 后，商的高位可转化为求 $B^{\ast }$ 在模 $x^k$ 下的逆。若已有精度 $m$ 的近似 $H_m$ 满足 $B^{\ast }{H}_m\equiv 1(\mathrm{mod}{x}^m)$，Newton 提升

把正确精度翻倍。各层乘法规模按几何级数增长，在标准 $M$ 假设下总成本为 $O(M(N))$；再将被除式的反转多项式乘以这个截断逆，截取并反转得到商 $Q$，最后计算 $A-BQ$ 得余式。公式要求常数项可逆，通常通过除数首项归一化保证，不能对一般含零因子的环无条件使用。

乘法因而成为子乘积树理路子乘积树Subproduct tree · Product tree for polynomial moduli自底向上合并线性因子或一般模多项式、供批量余式与插值复用的平衡乘积层次。、快速求值、插值、GCD、结式和精确线性代数的公共成本单位。实现上应按规模分层：小输入用 schoolbook 以避免递归开销，中等输入切换 Karatsuba 或 Toom，大输入在单位根与内存条件合适时使用变换。阈值来自实测，却不改变算法正确性；真正不可省略的是系数域假设、结果长度和精确性口径。