点表示法的操作 点表示的乘法 加法:只要是 degree- bound【幂次的上 类似地点表示法也可以方便地进行乘法 界】一样的具有相同点表示的多项式的加 若C(x)=A(x)B(x),则C(x)=A(XB()对 法,可以直接把其相关点的值相加即可。 于所有Xk都成 其复杂度为e(n) ·但我们必须 个问题:即C的 degree bound是A和B的和。 我们需要扩充A和B的点值对。 乘法(续) 系数表示多项式的快速乘法 ·扩充A的点对 戈们可以利用线形复杂度的点对表示多项 {(xXoy6),(X1,y1)…,(x2n1y2n1 式的乘法来实现系数表示多项式的快速乘 扩充B的点对 {(xX0y0),(x1y1)…(x2n1,y2n) 计算给定点集的值【如果选用合适点,其复杂 度engn)】 则C的点对表示 计算点值的乘法【e(n)】 ((o,yoyo), (X,,y1),.(X2n-1,y2,-1y2n-1)1 点值表示插值成系数表示法【如果选用合适算 其复杂度e(nlgn)】 示意图 DFT和FFT离散和快速傅立叶变换 ldpc 对于多项式,我们取x 的值为 ,其中a吨 Evalation Tene Bia g n) Tmn用 的第一个根 Pume-valce the principal nth root of unity: n阶主根 -i i ag4 点表示法的操作 • 加法：只要是degree－bound【幂次的上 界】一样的具有相同点表示的多项式的加 法，可以直接把其相关点的值相加即可。 • 其复杂度为θ(n) 点表示的乘法 • 类似地点表示法也可以方便地进行乘法， 若 C(x) = A(x)B(x), 则 C(xk) = A(xk)B(xk) 对 于所有 xk都成立 • 但我们必须面临一个问题：即 C的degree －bound是 A 和 B 的和。 • 我们需要扩充A和B的点值对。 乘法（续） • 扩充 A的点对, • {(x0,y0),(x1, y1),...,(x2n-1,y2n-1)}, • 扩充 B的点对 • {(x0,y' 0),(x1,y' 1),...,(x2n-1,y' 2n-1)}, • 则C 的点对表示 • {(x0,y0y' 0),(x1,y1y' 1),...,(x2n-1,y2n-1y' 2n-1)}. 系数表示多项式的快速乘法 • 我们可以利用线形复杂度的点对表示多项 式的乘法来实现系数表示多项式的快速乘 法。 – 计算给定点集的值【如果选用合适点，其复杂 度θ(nlgn）】 – 计算点值的乘法【θ(n）】 – 点值表示插值成系数表示法【如果选用合适算 法，其复杂度θ(nlgn）】 示意图 DFT和FFT离散和快速傅立叶变换 • 对于多项式，我们取x 的值为xi =ωn i ，其中ωn 是方程 • xn＝1 • 的第一个根 ￾ ωn ＝e2πι/n • the principal nth root of unity :n阶主根