HALF-GCD 算法的阐述

EntropyIncreaser 2020-03-11 9:39:08

翻了各课件,发现……

某个英文网站 是这么说的:

There is a way to calculate the GCD and resultants in O(n\log^2n) . To do this you should note that if you consider a(x)=a_0+x^ka_1 and b(x)=b_0+x^kb_1 where k=\min(\deg a,\deg b)/2 then basically the first few operations of Euclidean algorithm on a(x) and b(x) are defined by the Euclidean algorithm on a_1(x) and b_1(x) for which you may also calculate GCD recursively and then somehow memorize linear transforms you made with them and apply it to a(x) and b(x) 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 也写的比较晦涩,因此在这里稍微详细地谈谈,以正视听……


给多项式 a, b \in \mathbb F[z] ,我们原本的问题是求 GCD 以及扩展欧几里得的解: x, y\in \mathbb F[z], ax + by = \gcd (a, b)

由于多项式取模最坏情况下每次只让一个多项式的度数减小,这种方法的复杂度最好也就是 \Theta((\deg a) (\deg b)) 的。

我们考虑求解一个中间情况叫做 HALF-GCD,设 k = \min(\deg a, \deg b) ,这个东西让我们对于 a, b 能得到一个矩阵 \begin{pmatrix} x_1 & y_1 \\ x_2 & y_2 \end{pmatrix} ,其中 \deg x \le \frac k 2 + o(k) ,且 \deg (a x_1 + b y_1), \deg (a x_2 + b y_2) \le \frac k 2 + o(k) (除非它们的 \gcd \deg 比这个大)。也就是说这个 HALF-GCD 可以理解成是将欧几里得过程执行到一半的产物。

睿智的你想必已经意识到了这个东西如何得出真正的欧几里得的解。我们只需要调用一次这个算法,然后就规约到了一个 \frac n2 的子问题(可能需要额外支付 O(M(n)) 时间用于调整较大的多项式),那么我们就得到了一个 \Theta(M(n)) + T(n) + T(n/2) + T(n/4) + \cdots 的方法。

那么接下来考虑通过分治来解决 HALF-GCD:设 k=\min(\deg a, \deg b) ,我们首先算出 a/z^{k/2}, b/z^{k/2} 对应的矩阵,这样一个矩阵作用与原多项式有两部分:考虑将原来的表为 a=a_0 + a_1 z^{k/2}, b=b_0 + b_1 z^{k/2} ,那么 ax + by 中, \deg ((a_1 x + b_1 y)z^{k/2}) = \frac 34 k + o(k) ,另外 \deg (a_0 x + b_0 y) = \frac 34 k + o(k) 也比较显然。接着我们将得到的两个 \frac 34 k 次多项式除掉前 z^{k/4} 项送进去,这样又再次保证了递归返回的又是一个 \frac 14 k + o(k) 量级的结果,我们将两个矩阵相乘就得到了变换矩阵。而结果正好满足度数在 \frac k 2 + o(k) 以内。时间复杂度 T(n) = 2T(n/2) + M(n) ,即 M(n)\log n 。消耗了 M(n) 的一方面是进行矩阵乘法,另一方面是可能在一些情况减少两个多项式次数的差,同时也可能发生剪枝。

综上所述,我们在 M(n)\log n 的时间内完成了两个多项式的欧几里得求算,高精度整数的做法也是相似的。

这里 是一份代码,这里处理的时候是令 k = \max (\deg a, \deg b) ,理论上是差不多的,目前尚且不知道这个代码是否存在一些 edge case 上的问题,欢迎大家指正。