离散傅里叶变换(Discrete Fourier Transform) DFT ·输入：多项式的系数ao,a1,…,an p(x)= aixi =0 输出：选定x0,x1,…,xm为m+1次单位根，计算 p(xo),…,p(xm) 逆变换（插值） 输入：给定x0,X1,…,Xm为m+1次单位根， 以及p(xo),,p(xm) 输出：多项式的系数ao,a1,,an 22离散傅里叶变换 (Discrete Fourier Transform) DFT • 输入：多项式的系数�F, �(, … , �* � � = ; @AB C �@�@ • 输出：选定�E, �!, … , �H为m+1次单位根，计算 � �B , … , � �D 逆变换（插值） • 输入：给定�E, �!, … , �H为m+1次单位根， 以及� �B , … , � �D • 输出： 多项式的系数�E, �!, … , �$ 22