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.

翻译：通过将模块法与Ben-Or/Tiwari稀少的内插法相结合,提议对有限字段的多变量多元多数值采用对输入和产出敏感的GCD算法。这种算法略为复杂,而且对稀疏的表示十分敏感,而对于以前稀疏的GCD算法,只在一些特殊情况下才给出了复杂性。这表明新的算法在理论和实践上都优于现有的GCD算法:从四面形到线形的复杂程度下降,运行时间在各种基准中减少1-3级数量。