一种基于多样化多项式的高概率稀疏插值算法

作者：戚妞妞; 唐敏^*; 邓国强

来源：系统科学与数学, 2021, 41(12): 3324-3341.

• 稀疏多元多项式插值
• 多样化多项式
• 原根
• 离散对数

稀疏多元多项式插值用于构造黑盒函数,是求解多项式代数问题的一种有效策略,具有多项式时间复杂度的多元稀疏插值算法已得到广泛研究和使用.近期Huang(2021)提出了一个基于多样化多项式的稀疏插值算法,计算复杂度为O(nTlog2q+nT■logq),是有限域上首个关于变元个数n和项数界T的线性函数,关于次数界D的分数次幂的高效算法.由于Huang算法准确恢复黑盒多项式的成功率为3/4,为提高插值成功率,文章分析了Huang算法不能准确恢复黑盒多项式的三种情形,并给出相应的解决方案,基于此设计了一种基于多样化多项式的高概率稀疏插值算法,理论分析和数值实验证实了算法的可行性和有效性.

• 单位
  桂林电子科技大学