多项式乘法 给定：最多n次的多项式p(x),q(x)的系数 目标：求它们的乘积r(x)=p(x)q(x)的系数 想法： 1. 给定p(x),q(x)的系数 2. 令m≥2n+1,选定基点x0,x1,…,xm,计算p(xo),…,p(xm)和q(xo),,q(xm) 3. 计算r(x)=p(x)q(x) 4. 对{r(x)}插值，得到r(x)=p(x)q(x)的系数 愿望： 第2步只需要0(n log n) 第4步也只需要0(n log n) 这样总的步骤就只需要0(n log n) 18多项式乘法 给定：最多n次的多项式� � , �(�)的系数 目标：求它们的乘积 � � = � � �(�)的系数 想法： 1. 给定� � , �(�)的系数 2. 令� ≥ 2� + 1，选定基点�$, �%, … , �9，计算� �! , … , � �# 和 � �! , … , � �# 3. 计算� �$ = � �$ � �$ 4. 对 � �$ 插值，得到� � = � � �(�)的系数 愿望： • 第2步只需要�(� log �) • 第4步也只需要�(� log �) • 这样总的步骤就只需要�(� log �) 18