快速傅里叶变换(Fast Fourier Transform) 输入：n次多项式p(x)=∑oax 输出：p(x)在n+1次单位根上的值 FFT:分治 E(z)=a0+a2z+a4z2+a6z3+. 0(z）=a1+a3z+a5z2+a7z3+ 观察： p(z)=E(z2)+z0(z2) p({n+1次单位根)←E(n+1次单位根}2)，0(n+1次单位根)2) n+1次单位根}2={(n+1)/2次单位根} 特别地p(-z)=E(z2)-z0(z2) E(z),0(z)的次数为(n+1)/2次 FFT(ao,a1,an)←FFT(ao,a2,…),FFT(a1,a3,.) 24快速傅里叶变换 (Fast Fourier Transform) 24 输入：�次多项式� � = ∑"*$ ( �"�" 输出：� � 在n+1次单位根上的值 FFT：分治 � � = �$ + �&� + �D�& + �E�F + … � � = �% + �F� + �G�& + �H�F + … 观察: � � = � �& + � �(�&) � � + 1次单位根 ← � � + 1次单位根 & , �( � + 1次单位根 &) � + 1次单位根 &= (� + 1)/2次单位根 � � ， � � 的次数为 (� + 1)/2次 FFT(�$, �%, . . , �() ← FFT �$, �&, … , FFT(�%, �F, … ) 特别地 � −� = � �& − � �(�&)