• 论文 •

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

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

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

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.