Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.
翻译:已知的多元性乘数在密度大和稀少的情况下都具有准线性复杂性。 但对于这个问题,并没有给出真正的线性算法, 也没有给出真正的线性算法, 也不清楚它是否可能存在。 这为更简单的核查多元性产品问题提供了一个更好的算法空间。 虽然发现确定性方法似乎遥不可及, 但对于在代数操作数量上是最佳的问题, 存在着概率性算法。 我们研究这一问题的概括性, 以核查多元性产品模擬为稀薄的稀薄的稀释器。 我们调查了它对于稠密和稀散的多种复制品的微复杂性。 特别是, 当divisor 具有恒定的常温度和第二高度单度单项性时, 我们能够显示核查比模块化倍增倍增的优先性。 我们使用这些结果来获得关于标准多元性倍增倍增性核查的微复杂性的新界限。 特别是, 我们通过改进Kaminski 的结果和开发第一个准性微数项产品核查的准性多元性算法, 在密度大的情况下, 提供比复杂性模型模型的最佳算法。