No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial $F$. While computing the quotient Q=F quo G can be done in polynomial time with respect to the sparsities of F, G and Q, this is not yet sufficient to get a polynomial-time divisibility test in general. Indeed, the sparsity of the quotient Q can be exponentially larger than the ones of F and G. In the favorable case where the sparsity #Q of the quotient is polynomial, the best known algorithm to compute Q has a non-linear factor #G#Q in the complexity, which is not optimal. In this work, we are interested in the two aspects of this problem. First, we propose a new randomized algorithm that computes the quotient of two sparse polynomials when the division is exact. Its complexity is quasi-linear in the sparsities of F, G and Q. Our approach relies on sparse interpolation and it works over any finite field or the ring of integers. Then, as a step toward faster divisibility testing, we provide a new polynomial-time algorithm when the divisor has a specific shape. More precisely, we reduce the problem to finding a polynomial S such that QS is sparse and testing divisibility by S can be done in polynomial time. We identify some structure patterns in the divisor G for which we can efficiently compute such a polynomial~S.
翻译:没有已知的多元时间算法可以测试一个稀有的多元 G 偏差是否将另一个稀少的多元 G $F$分开。 当计算 Q 的数位数时, 以F、 G 和 Q 的宽度计算时, 这还不足以获得一个一般的多元时间分化测试。 事实上, Q 的宽度可能比 F 和 G 的要大得多。 在可喜的例子中, 商数的夸度是多元的, Q 最已知的计算 Q 的算法是非线性系数 # GQ, 复杂程度不理想。 在这项工作中, 我们对该问题的两个方面感兴趣。 首先, 我们提出一个新的随机算算算法, 两个稀少的多的多尼基数的数性比F, G 和 Q 的基数是准线性 。 我们的方法依赖于一个不易变的内基数 Q Q 结构, 而当我们用一个精确的内基调的内基值来测试时, 一个比任何卡度或卡度的变法 。