论文标题
多项式GCD在稀疏表示上的钻头复杂性
Bit Complexity of Polynomial GCD on Sparse Representation
论文作者
论文摘要
通过将模块化方法与BEN-OR/TIWARI稀疏插值相结合，提出了用于有限场上多种多项式多项式的输入和输出敏感的GCD算法。给出了算法的位复杂性，并且对稀疏表示敏感，而对于先前的稀疏GCD算法，仅在某些特殊情况下给出了复杂性。结果表明，新算法在理论上和实际上与现有的GCD算法相比是优越的：该程度的复杂性从二次到线性降低，并且在各种基准中，运行时间降低了1-3个数量级。
An input- and output-sensitive GCD algorithm for multi-variate polynomials over finite fields is proposed by combining the modular method with the Ben-Or/Tiwari sparse interpolation. The bit complexity of the algorithm is given and is sensitive to the sparse representation, while for previous sparse GCD algorithms, the complexities were given only in some special cases. It is shown that the new algorithm is superior both in theory and in practice comparing with existing GCD algorithms: the complexity in the degree is decreased from quadratic to linear and the running times are decreased by 1-3 orders of magnitude in various benchmarks.
