离散傅里叶变换(Discrete Fourier Transform) DFT ·输入：多项式的系数ao,a1,,an p(x)= ajx j=0 。 输出：选定xo,x1,…,xm为m+1次单位根，计算p(xo),,p(xm) 例子：计算[1,1,1,1]的DFT. p(x)=1+x+x2+x3 ·4次单位根={士1，士仍 p(1)=4 p(x)=0 otherwise 注意：书上的定义中还要除上Vn+1 21 离散傅里叶变换 (Discrete Fourier Transform) DFT • 输入：多项式的系数�!, �", … , �% � � = 7 ,LF * �,�, • 输出：选定�F, �(, … , �G为m+1次单位根，计算� �# , … , � �% 例子：计算 1,1,1,1 的DFT. • � � = 1 + � + �$ + �( • 4次单位根={±1, ±�} • � 1 =4 • � � =0 otherwise 注意：书上的定义中还要除上 � + 1 21