论文标题
基于多元化的稀疏多项式插值
Sparse Polynomial Interpolation Based on Diversification
论文作者
论文摘要
我们考虑在有限的领域上插值稀疏多元多项式的问题，该领域用黑框表示。在Ben-Or和Tiwari的算法上建立在具有特征性零的环上的多项式插值的基础上，我们通过进行其他探针在有限的场上开发了一种新的Monte Carlo算法。要插入f_q [x_1，\ dots，x_n] $的多项式$ f \，具有部分限制的$ d $和限制的$ t $，我们的新算法成本$ o ^\ logSim（nt \ log ^log ^2q+nt+nt+nt \ nt \ sqrt \ sqrt {d} d} \ log q q）$ 2（$ 2）$ 2（$ 2）$ 2（blamb $ 2）$ 2（blast $ 2（blast to）$ 2（如果$ q \ geq o（nt^2d）$，则返回正确的多项式具有恒定的成功率。与以前的一般有限字段算法相比，我们的算法在参数$ n，t，d $中具有更好的复杂性，并且是第一个达到$ d $的复杂性，同时将线性保持在$ n，t $中。一个关键技术是一种随机化，它使未知多项式的所有系数可区分，从而产生多种多样的多项式。 Giesbrecht和Roche在2011年提出了这种称为多元化的方法。我们的算法使用$ O（t）$探针独立地插入每个变量，然后使用多元化将术语与不同图像相关联。最后，我们通过求解离散对数并通过求解线性系统获得系数来获得指数。我们已经在枫树中实现了算法。实验结果表明，我们的算法可以应用于稀疏的多项式。我们还分析了算法的成功率。
We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari for interpolating polynomials over rings with characteristic zero, we develop a new Monte Carlo algorithm over the finite field by doing additional probes. To interpolate a polynomial $f\in F_q[x_1,\dots,x_n]$ with a partial degree bound $D$ and a term bound $T$, our new algorithm costs $O^\thicksim(nT\log ^2q+nT\sqrt{D}\log q)$ bit operations and uses $2(n+1)T$ probes to the black box. If $q\geq O(nT^2D)$, it has constant success rate to return the correct polynomial. Compared with previous algorithms over general finite field, our algorithm has better complexity in the parameters $n,T,D$ and is the first one to achieve the complexity of fractional power about $D$, while keeping linear in $n,T$. A key technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing a diverse polynomial. This approach, called diversification, was proposed by Giesbrecht and Roche in 2011. Our algorithm interpolates each variable independently using $O(T)$ probes, and then uses the diversification to correlate terms in different images. At last, we get the exponents by solving the discrete logarithms and obtain coefficients by solving a linear system. We have implemented our algorithm in Maple. Experimental results shows that our algorithm can applied to sparse polynomials with large degree. We also analyze the success rate of the algorithm.
