主根的一些性质 DET 多项式 A4(x) (o+m2)2=(o)2 计算其在点:0,o0……,on,上的值 ∑(o)=0如果k不是n的倍数 a Discrete Fourier Transform(DFT) Fast Fourier Transform(FFT) ·我们称y=(6,y1,…,ynd)是系数向量a 利用EF可以在nm)时间内计算DFTn(a)而 aoa1…,an)的离散傅立叶变换,记 FFT使用了 divide-and-conquer策略,把A(x)的 y= DFT,(a) 系数分为奇偶标号两类,然后定义两个 degree- bound为n2的多项式A0(x)和A(x) A0(x) t ax t A1(x) FFT续 RECURSIVE-FFT(a b n is a power of 2. then return a 故有 A(x)=A0(x2)+xA1(x2 6a←(a0,a2,…,an-2) 因此计算A(x)化简为只需计算A0(x)和 A1(x)在点 RECURSIVE-FFT(all (o0)2,(on1)2 10fork←0ton/2-1 上的值 yfo+oyk 14 return y b y is assumed to be column vector.5 主根的一些性质 ( ) 0如果k不是n的倍数 ( ) ( ) 1 1 0 / 2 2 2 2 / 2 = = = = − = ∑ − = + n j k j n k n k n n n n k n dk dn ω ω ω ω ω ω ω DFT ∑ ∑ − = − − = = = 1 0 1 n 1 n 0 n 1 0 y , ,......, , ( ) n j kj k j n n n j j j a A x a x ω 计算其在点：ω ω ω 上的值 多项式 Discrete Fourier Transform (DFT) Discrete Fourier Transform (DFT) • 我们称 y = (y0, y1, . . . , yn-1) 是 系数向量a = (a0, a1, . . . , an-1) 的离散傅立叶变换，记 为： • y = DFTn(a). Fast Fourier Transform (FFT) Fast Fourier Transform (FFT) • 利用FFT可以在 θ(n lg n)时间内计算 DFTn(a) 而 不是直接法的 θ (n2) • FFT 使用了 divide-and-conquer 策略, 把 A(x) 的 系数分为奇偶标号两类，然后定义两个 degree￾bound 为 n/2 的多项式 A[0](x) 和 A[1](x): FFT续 • 故有 • A(x) = A[0](x2) + xA[1](x2), • 因此计算A(x)化简为只需计算 A[0](x) 和 A[1](x)在点 • （ωn 0）2,（ωn 1）2,……., （ωn n－1）2， • 上的值