利用快速傅里叶变换(FFT)计算多项式乘法

1、利用快速傅里叶变换(FFT)计算多项式乘法作者：宋振华摘要本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的 时间复杂度降低为O(nlog2n),以便在计算机上高效计算多项式乘法.关键词：快速傅里叶变换、多项式乘法目录一、引言二、算法概述三、引理1、多项式的表小(1)系数表达形式(2)点值表达形式(3)插值2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式(1)单位复数根(2)离散傅里叶变换(DFT)(3)通过快速傅里叶变换(FFT)计算向量y3、利用FFT计算逆DFT,将结果的点值表达形式化为系数表达形式(1)在单位复数根处插值 利用FFT计算逆DFT四、

2、算法具体流程五、算法的实际应用：计算大整数乘法六、参考文献基于FFT的离散傅里叶变换(DFT)技术，是当今信息传输、频谱分析等领域中 最重要的数学工具之一.在计算机编程中，我们经常需要计算两个多项式函数的 乘积.对于两个n次多项式函数，计算其乘积最直接方法所需时间为 ©(n2).本文 将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的时间复杂 度降低为O(nlog2nh以便在计算机上高效执行.二、算法概述通过FFT进行离散傅里叶变换，将两个多项式由系数表达形式转化为点值表 达形式.将这2个点值表达形式的多项式相乘，得到结果的点值表达形式.最后利 用FFT做DFT的

3、逆,得到结果的系数表达形式.三、引理1、多项式的表小(1)系数表达n对于次数为n的多项式A(x)=£ aixi,其系数表达是一个由系数组成i =0的向量 a =(a0,a1,an T .考虑用系数形式表示、次数为n的多项式A(x)、B(x)的乘法运算.2ni记C(x) = A(x)B(x) =£ cixi.有G =£ ajb_j .可以看出，采取逐个计 i =0j -0算Ci (0 <i E2n,i w N)的方式进行求解，其时间复杂度为0(n2).(2)点值表达a.定义：一个次数为n的多项式A(x)的点值表达就是由一个有n个点值对组成的集合(x，y) |0

4、 S Mn,i w N, y = A(x),使得对于 k =0,1,2,.,n ,所有的xk各不相同.b.点值表达下多项式乘法对于n次多项式A(x), B(x),设其点值表达式分别为：A(x): (Xo, y0),(x1,y1),(x2,y2),(xn,yn),B(x): (Xo, yo),(X1,y1),(x2,y2), ,(xn,yn)设 C(x) = A(x)B(x),由于C(x)的次数为2n ,因此必须对A(x)和B(x)的点值表达式进行扩展,使每个多项式都包含2n +1个点值对.给定A , B的扩展点值表达：A(x): (Xo, yo),(Xi,yi),(X2,y2),(X2n,y2

5、n),B(x): (Xo, yo),(xi,yi),(x2,y2),(x2n,y2n).则C(x)的点值表达形式为：(xo,y0yo),(K,yiyi),(x2,y2y2),(x2n,y2ny2n) .因此，计算C(x)点值表达式的时间复杂度为O(n).插值求值运算的逆(从一个多项式的点值表达形式确定其系数表达形式)称为插值.下面将证明，n个点求值运算与插值运算是定义完备的互逆运 算.a.多项式的点值表达可以唯一确定多项式的系数表达形式.多项式的点值表达等价于矩阵方程：1Xo2Xo-n、 Xo3、1Xi2Xi-nXia1Yi1X22X2.nX2a2=y29aa*aI-9-Xn2Xn .nXn

6、J<an /<Yn)(3-1-3-a)记系数矩阵为V ,由Vandermonde亍歹!J式可知，v| = 口 (xi - xj ).0 M :二j 童而柏，j w n,0 Wi, j Wn,i# j ,有xi #Xj,因此 V #0,即 V 可逆.因此对于给定点值表达，我们能够唯一确定系数表达式，且a = V，y .b.对于次数为n的多项式函数A(x)，插值算法基于如下Lagrange公nA x ykk =0(x-Xj)j冰Xk - Xjjk(3-1-3-b)容易验证,Lagrange公式的计算复杂度为O(n2).因此，n个点求值运算与插值运算是定义完备的互逆运算,它们将多项式的系

7、数表达与点值表达进行相互转化.2、利用离散傅里叶变换（DFT）与FFT导出结果的点值表达形式（1）单位复数根n次单位复数根是满足0 n =1的复数切.n次单位复数根恰好有n个:i型对于 k=0,1,.,n1,这些根是 e n .由 Euler 公式 e旧=coSH ）+i sin（e ）可知，这n个单位复数根均匀地分布在以复平面原点为圆心的单位圆圆周 i红上.3=e n称为主n次单位根，所有其他n次单位根都是环的幕次.n个n次单位复数根00,与：，与：,.，0厂在乘法意义下构成一个群该群与群Zn, + n 同构.由此，可以得到如下推论生ki壁a. Vn AQk 占0,d >0,有切；：=

8、e dn =e n =s：.(3-2-1-a)nb. _ n = 2k, k N，tn = 2 - -1.(3-2-1-b)-2_一一 _ i 2nc.右 n=2k,kwN , (®n) |0 < i < n,i e N =( Wn/2) |0Wi< ,i N.2(3-2-1-c)对推论c的证明： 由a可知，/k w N，3：f ="；.所以又t于kw N,0Ek J,有(./2)22S2k如 _s2k n _ 2k _ *0k2 徨1下 。n。nn 。n (CJ n ) .，守Ut .n -1(3-2-1-d)d. Vn N*,kw N且k不能被n整除，

9、有Z n =0.i =0对推论d的证明:J n)k-1"n -1 离散傅里叶变换（DFT）n对于n次多项式A(x) =£ aixi , i z0其系数形式为a = （a0,a1,，an）T.(3-2-2-1)n设 yk=A(k)=" ai £1, 0 三 k En,k N ,(3-2-2-2)i =0则向量 y =2，%，yn)T(3-2-2-3)就是系数向量a=(%,ai,，4)T的离散傅里叶变换. 通过快速傅里叶变换(FFT)计算向量y .n对于n次多项式A(x) =£ aixi ,不妨假设n+1 = 2p, pw N .对于n+1i卫不为

10、2的整数次幕的情况类似，此处不再讨论.FFT采取了分治策略，采用A(x)中偶数下标与奇数下标的系数，分别定义两个新的n次多项式：2n-1A0(x) =a0 a2x ax2 an/x2 ,(3-2-3-1)n-1A1 (x)= a1 a3x a5x2 anx2 .(3-2-3-2)注意到A0(x)包含A所有偶数下标的系数，A1(x)包含A中所有奇 数下标的系数，于是有：A(x) = A0 (x2) xA1 (x2).(3-2-3-3)所以，求A(x)在可书:书，"书处的值的问题转化为:a.求次数为n的多项式A(x), A1(x)在点("书)2, ®：书)2,，2(&

11、quot;书)2处的取值.b.根据(2-2-3-3)综合结果.根据(2-2-1-c),式(2-2-3-3)不是由n+1个不同值组成，而是仅由叱1个次单位复数根所组成，每个根正好出现2次.因此，我们递归22地对次数为 色的多项式A0(x), A1(x)在色个金次单位复数根处222进行求值.这些子问题与原始问题形式相同，但规模变为一半.下面确定DFT过程的时间复杂度.注意到除了递归调用外，每次调用需要枚举a =(%©,，an)T中所有元素,将a划分为a°ao,a2；j- an、20=4自,8,，an，分别与多项式A0(x), A1(x)相对应.其时间复杂度为。(n).因此,对运

12、行时间有下列递推式(3-2-3-4)(3-2-3-5)T(n) =2T(n) E“n).2求解该递推式，有T (n) - L-)(n log2 n).采取快速傅里叶变换，我们可以在®(nlog2 n)时间内，求出次数为n 的多项式在n+1次单位复数根处的值.3、利用FFT计算逆DFTW结果的点值表达形式化为系数表达形式(1)在单位复数根处插值根据(2-1-3-a),我们可以把DFTW成矩P$乘积y =书a,其中Vn是一个由0n书适当幕次填充成的Vandermond即阵.。0111 -1 ,00y110 n+20n4* -8na1y2a=123 n+40n -+2n& n +a

13、a2.'1n0 n+2n«n +n2E n#)3n#0.即Vn4可逆.易知Vn 1(3-3-1-1)卜面证明Vnj(i, j)处元素Vjn4j1n 1(3-3-1-2)考虑Vn；Vn书(i, j)处元素Pj:n .北n(3-3-1-3) ' n 1 kj t pijn 1 =k =0n 1k =0当j =i时，pij =1;当j为时，根据(2-2-1-d)可知，Pj =0.(3-3-1-4)满足 Vn：Vn1 =I给定逆矩阵Vn；,可以求出a = (a°,a1,，4)T.(3-3-1-5) 利用FFT计算逆DFT比较(3-3-1-5)和(3-2-2-2)可知

14、，对FFT算法进行如下修改，即可计 算出逆DFT:把a与y互换，用切工替换o ,并且将计算结果每个元素除以n.因此，我们也可以在。(nlogzn)时间内计算出逆DFT.四、算法具体流程1、加倍多项式次数通过加入n个系数为0的高阶项，把多项式A(x)和B(x)变为次数为2n的 多项式，并构造其系数表达.2、求值通过应用2(n+1)阶的FFT计算出A(x)和B(x)长度为2(n +1)的点值表达.这些点值表达中包含了两个多项式在 2(n+1)次单位根处的取值.3、逐点相乘把A(x)的值与B(x)的值逐点相乘,可以计算出C(x) = A(x)B(x)的点值表达，这个表示中包含了 C(x)在每个2(n

15、+1)次单位根处的值.4、插值通过对2(n+1)个点值应用FFT,计算其逆DFT,就可以构造出多项式C(x) 的系数表达.由于1、3的时间复杂度为0(n),2、4的时间复杂度为Q(nlog2 n),因此整个算法的时间复杂度为G：，(nlog2 n).五、算法的实际应用：计算大整数乘法在密码学等领域中，经常需要进行大整数乘法运算.如果对整数p,q逐位相乘然后相加，其时间复杂度为O(log10 p 10g10 q).当p,q规模巨大时，这种算法将会 十分低效.因此，我们采取快速傅里叶变换进行优化.a p =an 10n +an,10n'十+a1 101 + a0,其中 0Wai <9

16、,ai= N,0<i <n,i = N(5-1)q =bm 10m +bm10mq+101 +b0,其中 0 Wbi <9,b e N,0<i <m,i = N(5-2)令多项式 A(x)=anxn agxn” ax1 a。，(5-3)B(x)=bmxm bm4xm4 - -bx1 b0.(5-4)(5-5)C(x)= A(x)B(x).注意至 1 p =A(10) , q =B(10).因此 pq =C(10) = A(10)B(10) .(5-6)将大整数相乘转化为多项式的乘法，应用快速傅里叶变换，即可得出结果.六、参考文献1、大学数学学习指南一一线性代数(第二版)，山东大学出版社，刘建亚, 吴臻，秦静，史敬涛,许闻天,张天德,金辉，胡发胜，宿洁，崔玉泉,蒋晓芸编著2、大学数学线性代数(第二版)，高等教育出版社，上海交通大学数学系 线性代数课程组