【学习笔记】Half-GCD - 码农知识堂

【学习笔记】Half-GCD

这里是一份快速讲解（即有些东西不严谨）。

最初看 $\sf Elegia$ 的博客，讲得倒是很好，就是留了个疑问未解决——我现在还在评论区里。

但看了 $\sf whx1003$ 的博客之后，该疑问就被解开了。因此可以认真讲讲。

算法动机：作除法时，计算商的复杂度是对的。但是每次的商太短，导致计算余数很慢；如果能够将多次取模统一计算，则可以加速。而且，计算商的时候，一般只会用到次数较高的项。

算法目标：对 $a,b\in{\Bbb F}[z]$ ，求矩阵
$[\begin{matrix} x_{1} & y_{1} \\ x_{2} & y_{2} \end{matrix}]$ $[x_{1} x_{2} y_{1} y_{2}]$ 使得
$\deg(x),\deg(ax_1{+}by_1),\deg(ax_2{+}by_2)\leqslant\frac{k}{2}+o(k)$

其中 $k=\max\{\deg a,\;\deg b\}$ 。当然 $x^2+y^2\ne 0$ 。

不难发现 $\deg\gcd(a,b)>\frac{k}{2}$ 时，该目标无法实现。因此，事实上它的目标是
$\deg(ax_1{+}by_1)\geqslant\frac{k}{2}\geqslant\deg(ax_2{+}by_2)$

然后再做了一次取模。而 $ax_2+by_2=0$ 时，实际上无法进行这次取模。

算法流程：设 $a=a_0+a_1z^{k/2},\;b=b_0+b_1z^{k/2}$ ，先求出 $a_1,b_1)$ 的 $\textit{Half-GCD}$ 结果，则对于每行的 $x, y$ ，有 $\deg(a_1x+b_1y)\leqslant\frac{k}{4}+o(k)$ ，且 $\deg(a_0x+b_0y)\leqslant\frac{3}{4}k+o(k)$ ，因而 $\deg(ax+by)\leqslant\frac{3}{4}k+o(k)$ 。

特别地，若此时求出的矩阵已经使得 $a_1x_1+b_1y_1=0$ 了，如果 $ax_1+by_1=0$ 就返回该矩阵即可，否则让 $ax_0+by_0)$ 对 $ax_1+by_1)$ 取模即可。

我们把两行乘出来的两个多项式，移除前 $\frac{k}{4}$ 项（即除以 $z^{k/4}$ 再去除负数次项），重新作 $\textit{Half-GCD}$ 。递归返回的多项式的度数是 $\frac{1}{4}k+o(k)$ 的，和上一个矩阵一样。通过类似的分析可知，这个矩阵对之前乘出的多项式进行变换后，度数是 ${1\over 2}k+o(k)$ 级别的。

所以两个矩阵相乘就是所需的结果——矩阵内元素的度数恰好是 $\frac{1}{2}k+o(k)$ 的。时间复杂度 $\mathcal T(n)=2\mathcal T({n\over 2})+\mathcal M(n)=\mathcal O(\mathcal M(n)\log n)$ ，其中 $\mathcal M(n)$ 是 $\deg=n$ 的多项式乘法的复杂度。

代码实现的技巧：在 $\textit{Half-GCD}$ 时，顺便返回矩阵与列向量的乘积。

下面是 $\sf whx1003$ 的讲解，我也摘抄一份。

记 $\mathbf M_G=$
$[\begin{matrix} G & 1 \\ 1 & 0 \end{matrix}]$ \;(G\in\mathbb F[x]) $M_{G} = [G 1 10] (G \in F [x])$ 是系数属于 $\mathbb F[x]$ 的矩阵，其中 $G\ne 0$ 且 $G$ 的最高次项系数为正。

考虑 $\gcd$ 的过程，每次求出商 $Q(x)=A(x)\div B(x)$ 后得到

$[\begin{matrix} B (x) \\ A (x) mod B (x) \end{matrix}]$ = $[\begin{matrix} 0 & 1 \\ 1 & - Q (x) \end{matrix}]$ $[\begin{matrix} A (x) \\ B (x) \end{matrix}]$ $[B (x) A (x) mod B (x)] = [01 1 - Q (x)] [A (x) B (x)]$

注意到该线性变换就是 $\mathbf M_Q^{-1}$ 。因此我们只需求出 $\prod\mathbf M_G$ ，即可直接计算出 $\gcd$ 的结果。

Comment. 事实上对于矩阵 $\mathscr A=$
$[\begin{matrix} a & b \\ c & d \end{matrix}]$ $A = [a c b d]$ ，若 $\det(\mathscr A)=s$ 则
$[\begin{matrix} d & - b \\ - c & a \end{matrix}]$
暴力展开不难验证。这可能是二阶矩阵逆元的速算方法吧。

称矩阵 $\mathscr A$ 是 $\rm regular$ 的，当且仅当 $\mathscr A$ 是若干 $\mathbf M_G$ 的乘积。注意 $\rm regular$ 矩阵未必是对称的。

稍微降低点要求，我们只希望求出 $\rm regular$ 矩阵 $\mathscr A$ 使得
$[\begin{matrix} C (x) \\ D (x) \end{matrix}]$ =\mathscr A^{-1} $[\begin{matrix} A (x) \\ B (x) \end{matrix}]$ $[C (x) D (x)] = A^{- 1} [A (x) B (x)]$ 满足 $\deg D(x)\leqslant\frac{1}{2}\deg A(x)$ 。这显然可行，因为最终 $D (x) = 0$ 。

Lemma 1.（ $\text{ordering property}$ ） $\rm regular$ 矩阵元素的 $\deg$ 在行和列上都单调不增，且其中非零元素的最高次项都为正。

归纳法不难证明之。事实上 $\rm regular$ 矩阵的 $\det=\pm 1$ ，因此其 $\deg$ 还有个等式关系。但是没啥用。

Lemma 2. 设 $\deg A>\deg B$ ，设 $m$ 是某常数而 $\mathscr A$ 是 $\rm regular$ 矩阵，令
$\mathcal A'=x^m\mathcal A'_0+\mathcal A'_1\\ \mathcal B'=x^m\mathcal B'_0+\mathcal B'_1$

其中

$[\begin{matrix} A_{j}^{'} \\ B_{j}^{'} \end{matrix}]$ = \mathscr A^{-1} $[\begin{matrix} A_{j} \\ B_{j} \end{matrix}]$ \quad\text{for }j=0,1 \tag{1} $[A_{j}^{'} B_{j}^{'}] = A^{- 1} [A_{j} B_{j}] for j = 0, 1 (1)$

其中 $A=x^mA_0+A_1$ 且 $B=x^mB_0+B_1$ ，满足 $\deg A_1,\deg B_1degA1,degB1<m$

Comment. 因为 $A^{'}$ 的记法似乎易引起歧义，我试图用 $\mathcal A$ 代替，但是二者的区分度又太低。我只好二者同时使用，并且不加 $(x)$ 以避免歧义。

若 $\deg\mathcal A'_0>\deg\mathcal B'_0$ 且 $\deg A_0\leqslant 2\deg\mathcal A'_0$ ，则
$\deg\mathcal A'=m+\deg\mathcal A_0'\\ \deg\mathcal B'\leqslant m+\max\{\deg\mathcal B_0',\;\deg(A_0){-}\deg(\mathcal A'_0){-}1 \}$

Proof. ~~可能把该引理读懂是最大的挑战~~。

对那些定义的直观感受：将 $A, B$ 按照 $x^m$ 分开后，分别进行 $\mathscr A$ 变换再合并。

对限制条件的直观感受：我们要做辗转相除，因此 $\deg A>\deg B$ 总成立。而 $\mathcal A_0'$ 不是特别短时，余数的次数由高次项决定。

现在开始证明。设 $\mathscr A=$
$[\begin{matrix} P & Q \\ R & S \end{matrix}]$ $A = [P R Q S]$ ，由 $(1)$ 式移项知 $A_0=P\mathcal A_0'+Q\mathcal B_0'$ ，由 $\text{Lemma 1}$ 和 $\deg\mathcal A'_0>\deg\mathcal B'_0$ 知
$\deg A_0=\deg\mathcal A'_0+\deg P \tag{2}$

联立 $2\deg\mathcal A'_0\geqslant\deg A_0$ 得
$\deg P\leqslant\deg\mathcal A'_0$

而 $\mathscr A^{-1}=\pm$
$[\begin{matrix} S & - Q \\ - R & P \end{matrix}]$ $A^{- 1} = \pm [S - R - Q P]$ ，因此 $\mathcal A_1=\pm(SA_1-QB_1)$ ，进而
$\begin{aligned} \deg A_{1}^{'} & ⩽ max {\deg A_{1} + \deg S, \deg B_{1} + \deg Q} \\ ⩽ max {\deg A_{1}, \deg B_{1}} + max {\deg S, \deg Q} \\ ⩽ m - 1 + \deg P \\ ⩽ m + \deg A_{0}^{'} \end{aligned}$

所以 $\deg\mathcal A'=m+\mathcal A'_0$ 。

同理可证 $\deg R=\deg B_0-\deg\mathcal A'_0\leqslant\deg A_0-\deg\mathcal A'_0$ 以及

$\begin{aligned} \deg B_{1} & ⩽ max {\deg A_{1} + \deg R, \deg B_{1} + \deg P} \\ ⩽ max {m - 1 + \deg A_{0} - \deg A_{0}^{'}, m - 1 + \deg P} \\ ⩽ m - 1 + \deg A_{0} - \deg A_{0}^{'} \end{aligned}$ $de g B_{1} ⩽ max {de g A_{1} + de g R, de g B_{1} + de g P} ⩽ max {m - 1 + de g A_{0} - de g A_{0}^{'}, m - 1 + de g P} ⩽ m - 1 + de g A_{0} - de g A_{0}^{'}$

注意前提条件 $\deg A>\deg B$ 保证了 $\deg A_0\geqslant\deg B_0$ ，以及 $(2)$ 式在此处的运用。 $\blacksquare$

接下来给出 $\textit{Half-GCD}$ 的伪代码实现：

$\begin{aligned} A l g o r i t h m hgcd (A, B) \\ 1 & m \leftarrow ⌈ \frac{\deg (A)}{2} ⌉ \\ 2 & i f \deg (B) < m t h e n \\ 3 & r e t u r n [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] \\ 4 & H \leftarrow h g c d (A \div x^{m}, B \div x^{m}) \\ 5 & [\begin{matrix} C \\ D \end{matrix}] \leftarrow H^{- 1} [\begin{matrix} A \\ B \end{matrix}] \\ 6 & i f \deg (D) < m then \\ 7 & r e t u r n H \\ 8 & [\begin{matrix} Q \\ R \end{matrix}] \leftarrow [\begin{matrix} C \div D \\ C mod D \end{matrix}] \\ 9 & i f \deg (R) < m t h e n \\ 10 & r e t u r n H \cdot M_{Q} \\ 11 & k \leftarrow 2 m - \deg (D) \\ 12 & S \leftarrow h g c d (D \div x^{k}, R \div x^{k}) \\ 13 & r e t u r n H \cdot M_{Q} \cdot S \end{aligned}$ $12345678910111213 Algorithm hgcd (A, B) m \leftarrow ⌈ \frac{d e g ( A )}{2} ⌉ if de g (B) < m then return [1001] H \leftarrow hgcd (A \div x^{m}, B \div x^{m}) [C D] \leftarrow H^{- 1} [A B] if de g (D) < m then return H [Q R] \leftarrow [C \div D C mod D] if de g (R) < m then return H \cdot M_{Q} k \leftarrow 2 m - de g (D) S \leftarrow hgcd (D \div x^{k}, R \div x^{k}) return H \cdot M_{Q} \cdot S$

特别地，当 $A, B$ 最高次项系数为负时，应将系数取反即乘 $- 1$ ，反正 $- 1$ 是 $\rm unit$ 。

Theorem. $\mathrm{hgcd}(A,B)$ 返回的 $\rm regular$ 矩阵 $\mathscr S$ 满足：令
$[\begin{matrix} A^{'} \\ B^{'} \end{matrix}]$ =\mathscr S^{-1} $[\begin{matrix} A \\ B \end{matrix}]$ $[A^{'} B^{'}] = S^{- 1} [A B]$ 则 $\deg\mathcal A'\geqslant\lceil\frac{\deg A}{2}\rceil>\deg\mathcal B'$ 。

Proof. 该限制条件的好处是：上面算法中 $\mathscr H$ 作用在
$[\begin{matrix} A \\ B \end{matrix}]$ $[A B]$ 上时， $\text{Lemma 2}$ 的限制条件即成立（其中的 $m$ 与算法中的 $m$ 相同）。

考虑每个 $\mathbf{return}$ 语句的返回值是否满足条件。第 $3$ 行上的显然合法。第 $7$ 行上的，由 $\text{Lemma 2}$ 可知 $\deg C=m+\deg\mathcal A_0'\geqslant m$ ，故合法。第 $10$ 行上的，由第 $6$ 行的 $\mathbf{if}$ 知 $\deg D\geqslant m>\deg R$ ，故合法。

关键在最后。令 $m'=\deg A_0=\deg(A)-m$ ，对 $\deg A$ 进行归纳法，由归纳假设知 $\deg\mathcal B'_0<\lceil\frac{m'}{2}\rceil\leqslant\deg\mathcal A'_0$ ，再由 $\text{Lemma 2}$ 得

$\begin{aligned} \deg D & ⩽ m + max {\deg B_{0}^{'}, \deg (A_{0}) - \deg (A_{0}^{'}) - 1} \\ ⩽ m + max {⌈ \frac{m^{'}}{2} ⌉ - 1, ⌊ \frac{m^{'}}{2} ⌋ - 1} \\ = m + ⌈ \frac{m^{'}}{2} ⌉ - 1 < 2 m \end{aligned}$ \tag{3} $de g D ⩽ m + max {de g B_{0}^{'}, de g (A_{0}) - de g (A_{0}^{'}) - 1} ⩽ m + max {⌈ \frac{m ^{'}}{2} ⌉ - 1, ⌊ \frac{m ^{'}}{2} ⌋ - 1} = m + ⌈ \frac{m ^{'}}{2} ⌉ - 1 < 2 m (3)$

于是 $11$ 行的赋值能够使 $k > 0$ 。而第 $9$ 行的 $\mathbf{if}$ 指明 $\deg D>\deg R\geqslant m$ ，故 $\deg D>2m-\deg D=k$ ，因此第 $12$ 行的 $\mathrm{hgcd}$ 调用至少是合法的。

现在考虑第二次 $\rm hgcd$ ，相同记法得到 $D_0,\mathcal D'_0$ 等。此时有
$\deg\mathcal D'_0\geqslant\left\lceil{\deg D_0\over 2}\right\rceil>\deg\mathcal R_0'$

因为 $(3)$ 式已经说明 $\deg D\leqslant m+\lceil{\deg(A)-m\over 2}\rceil-1<\deg A$ ，归纳假设仍然成立。

而 $deg D_0=\deg(D)-k=2\deg(D)-2m$ ，于是
$\deg\mathcal D'_0\geqslant\deg(D)-m>\deg\mathcal R'_0$

再由 $\text{Lemma 2}$ 得
$\deg\mathcal D'=k+\deg\mathcal D'_0\geqslant k+\deg(D)-m=m$

与

$\begin{aligned} \deg R^{'} & ⩽ k + max {\deg R_{0}^{'}, \deg (D_{0}) - \deg (D_{0}^{'}) - 1} \\ ⩽ k + max {\deg (D) - m - 1, \deg (D) - m - 1} \\ = m - 1 \end{aligned}$ $de g R^{'} ⩽ k + max {de g R_{0}^{'}, de g (D_{0}) - de g (D_{0}^{'}) - 1} ⩽ k + max {de g (D) - m - 1, de g (D) - m - 1} = m - 1$

第二行中同时代入了
${\begin{cases} \deg D_{0} = 2 \deg (D) - 2 m \\ \deg D_{0}^{'} ⩾ \deg (D) - m \end{cases}$ ${de g D_{0} = 2 de g (D) - 2 m de g D_{0}^{'} ⩾ de g (D) - m$ ，但这应该不会给读者带来困扰。 $\blacksquare$

显然返回的矩阵中多项式的次数是 $\mathcal O(\deg A)$ 的，因为我们实质上在做辗转相除。由 $(3)$ 式还可知 $\deg D\leqslant m+\lfloor{m'\over 2}\rfloor$ ，因此 $12$ 行递归到了度数只有 $A$ 的一半的多项式。

故 $\textit{Half-GCD}$ 算法的复杂度为 $\mathcal O(n\log^2 n)$ ，如果我们认为多项式运算的复杂度是 $\mathcal O(n\log n)$ 的。
相关阅读:
JSR303是啥？有啥用处？
python+nodejs+vue教材征订管理系统
 后知后觉的尴尬
 群狼调研开展连锁酒店神秘顾客调查项目
 golang工程——grpc服务健康检查
 【Golang】网络编程
 TP4333移动电源芯片
 JSON 格式化和校验工具
 spring各版本jar包下载，持续更新中
 Linux Kprobes探索与实践一
原文地址：https://blog.csdn.net/qq_42101694/article/details/126333577