论文标题
稀疏的多项式插值和软线性时间分裂
Sparse Polynomial Interpolation and Division in Soft-linear Time
论文作者
论文摘要
如果是通过整数系数评估未知多项式的方法，我们提出了新算法以恢复其非零系数和相应的指数。作为应用程序，我们将此插值算法调整为计算两个给定多项式的确切商的问题。这些方法根据稀疏表示的比特长度有效，即非零项的数量，系数的大小，变量的数量和程度的对数。我们的结果的核心是一种新的蒙特卡洛随机算法，用于恢复具有整数系数的多项式$ f（x）$，以评估任何选择的整数$θ$和$ m $的方法来评估$ f（θ）\ bmod m $。该算法具有几乎最佳的位复杂性，这意味着探针的总比特长度以及计算运行时间是在产生的稀疏多项式的位长度中柔和的线性（忽略对数因子）。据我们所知，这是第一个稀疏的插值算法，在总输出尺寸中具有软线性位复杂性。对于具有整数系数的多项式，最好的先前已知结果至少对指数的比特长度至少具有依赖性。
Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. These methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover a polynomial $f(x)$ with integer coefficients given a way to evaluate $f(θ) \bmod m$ for any chosen integers $θ$ and $m$. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with soft-linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents.
