论文标题
基于导数的稀疏多项式插值
Sparse Polynomial Interpolation Based on Derivative
论文作者
论文摘要
在本文中，我们提出了两种新的以直线程序（SLP）为代表的稀疏多元多项式的新插值算法。我们的这两种算法都可以在任何有限字段$ f_q $上起作用，具有较大的特征。第一个是蒙特卡洛随机算法。它的算术复杂性在$ f $的非零条款的数字$ t $中是线性的，在变量的数字$ n $中。如果$ q $是$ o（（ntd）^{（1）}）$，其中$ d $是部分学位的绑定，那么我们的算法比其他现有算法具有更好的复杂性。第二个是确定性算法。它比具有较大特征的领域的现有确定性算法具有更好的复杂性。它的算术复杂性在$ n，t，\ log d $，即稀疏表示的大小中是二次的。我们还表明，确定性算法的复杂性与Bläser等人的确定性零测试之一相同。对于有限场上的SLP给出的多项式（对于大特征）。
In this paper, we propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program(SLP). Both of our algorithms work over any finite fields $F_q$ with large characteristic. The first one is a Monte Carlo randomized algorithm. Its arithmetic complexity is linear in the number $T$ of non-zero terms of $f$, in the number $n$ of variables. If $q$ is $O((nTD)^{(1)})$, where $D$ is the partial degree bound, then our algorithm has better complexity than other existing algorithms. The second one is a deterministic algorithm. It has better complexity than existing deterministic algorithms over a field with large characteristic. Its arithmetic complexity is quadratic in $n,T,\log D$, i.e., quadratic in the size of the sparse representation. And we also show that the complexity of our deterministic algorithm is the same as the one of deterministic zero-testing of Bläser et al. for the polynomial given by an SLP over finite field (for large characteristic).
