翻了各课件,发现……
某个英文网站 是这么说的:
There is a way to calculate the GCD and resultants in
. To do this you should note that if you consider and where then basically the first few operations of Euclidean algorithm on and are defined by the Euclidean algorithm on and for which you may also calculate GCD recursively and then somehow memorize linear transforms you made with them and apply it to and to lower the degrees of polynomials. Implementation of this algorithm seems pretty tedious and technical thus it's not considered in this article yet.
你如果脑子一冲,傻乎乎地去直接分治一半算出线性变换,DEBUG 一下会让你冷静过来…… 你发现这个线性变换应用到整体多项式上没有任何效果……
而 Picks 的 Introduction to Polynomials 也写的比较晦涩,因此在这里稍微详细地谈谈,以正视听……
给多项式
由于多项式取模最坏情况下每次只让一个多项式的度数减小,这种方法的复杂度最好也就是
我们考虑求解一个中间情况叫做 HALF-GCD,设
睿智的你想必已经意识到了这个东西如何得出真正的欧几里得的解。我们只需要调用一次这个算法,然后就规约到了一个
那么接下来考虑通过分治来解决 HALF-GCD:设
综上所述,我们在
这里 是一份代码,这里处理的时候是令