Definition

多项式乘法是指把第一个多项式的每一项与第二个多项式的每一项相乘（反复运用分配律），然后合并同类项；结果的次数等于两个因式次数之和，平方差或完全平方三项式等特殊模式可以加快常见情形的运算。严格地说，对 $f = \sum a_ix^i$ 和 $g = \sum b_jx^j$ 而言，乘积为 $(fg)(x) = \sum_{k} \left(\sum_{i+j=k} a_ib_j\right) x^k$，即系数序列的柯西积（卷积）；利用快速傅里叶变换，多项式乘法可以在 $O(n \log n)$ 时间内完成，这也是快速整数乘法算法的基础。