• 论文 • 上一篇    下一篇

一种基于竞争策略的稀疏多元多项式插值算法

邓国强,唐敏,张永燊   

  1. 桂林电子科技大学广西密码学与信息安全重点实验室, 桂林 541004
  • 出版日期:2018-12-25 发布日期:2019-02-22

邓国强,唐敏,张永燊. 一种基于竞争策略的稀疏多元多项式插值算法[J]. 系统科学与数学, 2018, 38(12): 1436-1448.

DENG Guoqiang,TANG Min, ZHANG Yongshen. A Sparse Polynomial Interpolation Based on Racing Strategy[J]. Journal of Systems Science and Mathematical Sciences, 2018, 38(12): 1436-1448.

A Sparse Polynomial Interpolation Based on Racing Strategy

DENG Guoqiang ,TANG Min, ZHANG Yongshen   

  1. Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electrical Technology, Guilin 541004
  • Online:2018-12-25 Published:2019-02-22

提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法, 改进了Javadi和 Monagan在2010年提出的概率性插值算法. 对$n$个变元, $t$个非零项 的多元多项式$f$进行插值, Javadi/Monagan算法要求给定$f$的全次数上界$d$, 为确定变元$x_j$在第$i$个单项式中的次数, 需要从$0$到$d$做$d+1$次根测试, 每个变元测试次数为${\bm O}(td)$. 改进算法设计了两个子算法并采用竞争策略用尽可能少的插值点准确计算变元$x_j$在多项式$f$中的次数集, 使得测试次数降为${\bm O}(td')$, 其中$d'$为变元$x_j$在$f$中出现的次数集的基数, 因而减小了测试次数及根冲突的概率. 在Maple环境下实现了改进算法, Zippel算法和Javadi/Monagan算法, 给出了测试用例对3种算法的插值点个数及其CPU运行时间进行了比较.

In this paper, we present a sparse polynomial interpolation algorithm based on racing strategy over finite fields. Our algorithm modifies the probabilistic algorithm of Javadi and Monagan from 2010 for interpolating polynomials. To interpolate a polynomial $f$ in $n$ variables with $t$ non-zero terms, Javadi/Monagan algorithm requires $d$ the bound on the degree of $f$ to be given in advance. To determine the degrees of each monomial of $f$ in each variable, Javadi/Monagan algorithm needs to check the roots using ${\bm O}(td)$ probes in a loop from $0$ to $d$. The improved algorithm contains two sub-algorithms and uses racing strategy to compute the exact degrees of each monomial of $f$ in $x_j$ as small as probes possible. The total tests turn to be ${\bm O}(td')$, where $d'$ is the cardinality of degree set of each variable in $f$. Thus the total tests and the probability of root clash of the improved algorithm are decreased. We have implemented the improved algorithm, Zippel's algorithm and Javadi/Monagan algorithm in Maple. In the paper, we provide benchmarks comparing the number of probes and CPU running time our algorithm does with both Zippel's algorithm and Javadi/Monagan algorithm.

()
[1] 戚妞妞, 唐敏, 邓国强. 一种基于多样化多项式的高概率稀疏插值算法[J]. 系统科学与数学, 2021, 41(12): 3324-3341.
阅读次数
全文


摘要