### Sparse Multivariate Polynomial Interpolation over Finite Fields

TANG Min, DENG Guoqiang+

1. Guangxi Key Laboratory of Cryptography and Information Security, School of Mathematics & Computing Science, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
• Online:2019-02-01 Published:2019-01-25

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

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

Abstract: Sparse interpolation is an effective method to reduce the time complexity of computer algebraic algorithms. It has been widely used in the fields of signal processing, compressed sensing, resultant computation, image processing and so on. In order to improve the efficiency of sparse multivariate polynomial interpolation algorithms, an improved sparse interpolation algorithm addressed by Javadi and Monagan is presented. Firstly, the restriction on [T], which is the bound on the number of terms and necessary condition in the original method, has been eliminated. In fact, the exact number of terms in [f] can be obtained by computing the determinant of special defined matrix. Secondly, the necessary condition that the degree bound [D] in [f] must be given in advance has been also eliminated. The exact degree of [f] is obtained by forming an auxiliary function, applying the high probabilistic method, and combining with early termination technique in Cauchy interpolation. Thus the problem of high computational complexity caused by the bad degree bound [D] in Javadi/Monagan algorithm is solved. Compared to Javadi/Monagan algorithm, the theory analysis and experiment results reveal that the performance has been highly improved by applying new algorithm, especially when the given degree bound is too high. Furthermore, the improved algorithm does not need [T] and [D] in advance, so it is more practical to use the interpolation recovery or approximation for real problems.