本章涉及知识点：
1、多项式乘法的时间复杂度
2、多项式的表示：系数
3、多项式的表示：点值
4、复数的表示
5、单位复数根
6、单位复数根的性质—消去引理
7、单位复数根的性质—折半引理
8、离散傅里叶变换：DFT和IDFT
9、快速傅里叶变换：FFT
10、FFT求解多项式乘法的步骤
11、python编程实战FFT大数乘法
12、结果分析
一、多项式乘法的时间复杂度
数学中，我们可以将任意一个n位的数字写为一个n-1次多项式，如456可以写为
即可抽象定义出以x为变量的多项式函数A(x)
其中aj表示：长度为N-1位数字的第j为数字
例如要计算456 * 123 = ？，则我们用多项式A(x)和B(x)来分别表示其各自的数字，C(x)表示两个多项式的乘积
由乘法的运算规则，两个数的每一位数字都要与另一个数的每一位相乘，最后相加同一位上所有的数字，得到乘积中该位的数字，即
将x=10为基带入结果，即可以得到456 * 123 = 4 * 10**4 + 13 * 10**3 + 28 * 10**2 + 27 * 10 + 18 = 56088
我们可以归纳出乘积C(x)的每一位数字的计算关系为
其中cj表示：乘积数中的第j位的数字
则乘积多项式C(x)可以写为
至此我们可以看到，由于受限于乘法运算自身的规则，计算两个多项式乘积（将数字转换为多项式）的时间复杂度为：，当n很大的时候复杂度将非常高
那么需要研究的问题就是：有没有方法可以高效的提高多项式乘法复杂度呢？
二、多项式的表示：系数
为了降低多项式乘法的复杂度，我们首先需要了解几个数学知识
从多项式函数的定义，我们将所有系数视为系数向量，而由全部系数组成的向量a叫做该多项式的系数表达
PS：乘积多项式C(x)的系数向量cj，也称输入向量a和b的卷积，记为
从之前的分析可知，要计算出乘积C(x)的每一个系数向量cj，需要的时间复杂度为
三、多项式的表示：点值
我们任意选取n个不同的自变量x带入多项式函数A(x)进行求值运算，将得到n个不同数值的y，即
则多项式的点值表达就是由这n个数值点组成的集合
因为可以选取任意n个不同点所构成的集合，所有一个多项式可以有很多不同的点值表达
我们把任意n个点构成的集合叫做点值表达的基
从点值表达的基入手，选取适当的xk来优化多项式乘法效率，为此，我们选取单位复数根作为多项式的基
四、复数的表示
复数的定义：设a，b为实数，则形如的数称为复数，其中a称为实部，b称为虚部
PS：当a=0时，复数为纯虚数；当b=0时，复数可视为实数
将复数的实部与虚部的平方和的正平方根值称为该复数的模，即
五、单位复数根
任意一个复数w，其n次幂的结果为1，就称复数w是n次单位复数根，即
可以看到，n次单位复数根有n个，其几何意义为：n个单位复数根均匀的分布在以复平面原点为圆心的单位圆上
在几何意义的单位圆中，我们将圆周角均分成n份，则
叫做单位根的幅角
由欧拉公式得
我们定义表示一个n次单位根，则
又被称为主n次单位根，而其余
、
等叫做n次单位根的幂次，记为：
，则
可以很容易知道
下面我们证明n次单位根的两个性质
六、单位复数根的性质—消去引理
设d>0为任何一个整数，则
七、单位复数根的性质—折半引理
由
则可以得到
至此，可以看到通过消去和折半引理，我们将n的规模降低到了原来的一半
八、离散傅里叶变换：DFT和IDFT
回顾之前我们的多项式函数
我们将n次单位根的幂次项：依次带入A(x)，则得到
记向量是系数向量
的离散傅里叶变换，也称离散傅里叶正变换（DFT）
则对应的离散傅里叶逆变换（IDFT）为
可以看到：
（1）DFT对应着多项式求值
（2）IDFT对应着插值，即求多项式的系数
九、快速傅里叶变换：FFT
由DFT定义可知，将全部依次带入A(x)计算出多项式的时间复杂度仍然是
此时我们就需要利用之前所讲的n次单位复数根的知识，将A(x)中的偶数下标和奇数下标的系数，分别用两个新的多项式A1(x)和A2(x)来表示，即
注意：A(x)的次数界为n，A1(x)的次数界为n/2，A2(x)的次数界也为n/2
则可以得到A(x)和A1(x)、A2(x)的关系为
我们将带入得，其中
至此，我们就得到了在之间
的所有求值
下面还需要计算之间的
的值，根据折半引理，我们将
带入得
至此，我们就得到了之间
的所有求值
观察上面两个式子，不难发现：
（1）
和
的计算式子里只有一个常数项互为相反数
（2）在
之间枚举出
后，就可以在
的时间里得到
的
（3）原问题的规模缩小了一半（分治法的思想）
至此，我们利用数学中n次单位复数根的性质，将DFT优化为FFT（快速傅里叶正变换），即
十、FFT求解多项式乘法的步骤
通过以上的研究，我们可以总结出使用FFT计算多项式乘法的时间复杂度
FFT利用n次单位复数根和分治法的思想，将多项式乘法的时间复杂度由降低到了
最后我们可以总结出求解多项式乘法的高效算法步骤为：
（1）加倍次数界：由分治法的思想，将两个多项式的次数界补全为2的幂次
（2）求值：通过FFT计算出两个多项式的点值表达，即2n次单位复数根的多项式函数取值
（3）逐点相乘：将两个多项式的点值依次相乘，得到相乘结果的点值
（4）插值：通过IDFT计算相乘结果的点值，得到相乘结果的每一个系数
十一、python编程实战FFT大数乘法
十二、结果分析
我们随便用两个386位和422位的整数，进行下面实验比较计算乘法的时间消耗
（1）不使用矩阵乘法的离散傅里叶变换DFT
（2）使用矩阵乘法的离散傅里叶变换DFT
（3）使用矩阵乘法的快速傅里叶变换FFT
（4）直接使用numpy封装的FFT
运行代码，实验结果如下
至此，我们可以总结出
（1）FFT采用分治算法的思想，利用数学中n次单位复数根的性质，将时域转化为频域，再到频域转化为时域，非常高效的提高了多项式乘法效率！
（2）我们根据数学理论一步步封装的FFT和numpy封装的FFT性能上非常接近
案例代码见：大数乘法—多项式与快速傅里叶变换
