有限域上稀疏多元多项式插值算法*

唐 敏，邓国强

桂林电子科技大学 数学与计算科学学院 广西密码学与信息安全重点实验室，广西 桂林 541004

1 引言

插值是函数逼近的重要方法，利用它可通过函数在有限个点处的取值情况，估算出函数在其他点处的近似值。在信号处理[1]、不确定性量化[2-4]、压缩感知[5]、图像处理[6-7]等领域需要有效地利用较少的函数值恢复一个函数，而这个函数往往具有稀疏的表示形式，稀疏插值能有效地处理此类问题。稀疏多元多项式插值是一种降低计算机代数算法时间复杂度的有效方法，是稀疏有理函数插值[8]及稀疏隐函数插值[9]的基本步骤，应用在结式计算[9]、多元多项式GCD计算[10-12]、方程求根、数值微分、数值积分、曲面的外形设计和有限元法及上述提及的诸多应用领域。因此提高稀疏多元多项式插值的效率十分有意义。

对于多元多项式，稠密插值所需的插值点个数为(d+1)n，其中d是变元的次数，n是变元的个数。研究工作表明，多元多项式插值算法的计算复杂度与变元个数可以不呈指数关系，而是与目标多项式的稀疏性相关，即是关于n、d、t和lbp的多项式函数，其中t是目标多项式的项数，素数p是有限域的特征。

1979年Zippel提出了第一个具有多项式时间复杂度的稀疏多元多项式插值算法[12]。该算法基于这样的假设：如果在一个随机的赋值点处多项式的取值为零，那么它就是一个零多项式。由于这个结论的成立是高概率的，因此Zippel算法是一个概率性的方法。在执行上，Zippel算法顺序地对每个变元逐一插值，不能并行化，插值点个数为ndt，时间复杂度为O(ndt3)。……