关于非递归exgcd写法中式子的推导

事情是这样的:最近某个老师要求实现一个适用于任意大数的$exgcd$。

说是上课时用他造的数据测试、演示。然而想想也知道,$exgcd$的复杂度在$O(log n)$级别,他要是给我个$10000$位的数字岂不是要当场爆掉常见的递归写法?
于是我决定改成非递归形式的实现。网上确实有现成的Python代码,但是他们几乎都长这个样子:

def exgcd(a,b):
    u,  v,  s,  t = 1, 0, 0, 1
    while b !=0:
        q, r = divmod(a,b)
        a, b = b, r
        u, s = s, u - q*s
        v, t = t, v - q*t

    return (u, v, a)

求$gcd$的部分很容易看明白,但是后面的$s’ = u-qs,t’ = v – qt$是干什么的?
想着看看网上有没有推导,倒是找到了一篇,但是列表格我觉得实在是太丑了orz……
题外话不多说,进入正文,这里给出一种直观的方式。
PS:其实这对熟悉线代的人来说这应该不算是什么问题……不过我的线代好辣鸡啊TAT

怎么改写?

我们熟知,对于整数$a,b$,有:
$$
(\ a\ ,b\ ) = (\ b\ ,\ a \% b\ )
$$

因此我们可以这样进行迭代:每次令$a’ = b,b’ = a\ \%\ b = a – qb $,其中$q = \lfloor\frac{a}{b}\rfloor$.
我们把它写成矩阵的形式:
$$
\begin{pmatrix}0 && 1 \\1 && -q \\\end{pmatrix}
\cdot\begin{pmatrix}a \\b \\\end{pmatrix}=\begin{pmatrix}b \\a – qb \\
\end{pmatrix}
$$

这个形式意味着我们可以不断地左乘矩阵
$$
X_{i} = \begin{pmatrix}
0 && 1 \\
1 && -q_{i} \\
\end{pmatrix}
$$
直到$a- q_{n}b = 0$.
也就是说,如果我们能够直接算出左侧的所有矩阵,即如果我们最后得到
$$
\begin{pmatrix}
u && v \\
s && t \\
\end{pmatrix}
\cdot
\begin{pmatrix}
a \\
b \\
\end{pmatrix}
$$
这样的形式,那么最后一定满足$ua + vb = (a,b)$, $sa + tb = 0$.我们就求出了我们需要的$u和v$.
但是左边的矩阵中,$q_{i} = a_{i} / b_{i}$,这意味着我们要么先把这些矩阵按顺序存下来,然后倒序逐个相乘,要么我们还得考虑递归的形式。这样做似乎并没有得到改善。
有没有更好的方法呢?
事实上,解决方案很简单。考虑分块矩阵
$$
A =
\begin{pmatrix}
a && 1 && 0\\
b && 0 && 1\\\end{pmatrix}=
\left(
\begin{array}{c|c}
\boldsymbol{a} & E
\end{array}
\right)
$$
左乘$X$,有
$$
XA =
\left(
\begin{array}{c|c}
X\boldsymbol{a} & X
\end{array}
\right)
$$

不断地左乘,我们得到
$$
X_{n}X_{n-1}\cdots X_{1}A =
\left(
\begin{array}{c|c}
X_{n}X_{n-1}\cdots X_{1}\boldsymbol{a} & X_{n}X_{n-1}\cdots X_{1}
\end{array}
\right)
$$

这样我们就可以在一次迭代中做完所有的工作了。

最后推导式如下。记中途时刻为
$$
\begin{pmatrix}
a && u && v\\
b && s && t\\
\end{pmatrix}
$$

左乘$X$,得到
$$
\begin{pmatrix}
b && s && t\\
a-qb && u-qs && v-qt\\
\end{pmatrix}
$$

其中,初始时,$u,v,s,t = 1,0,0,1$

参考

此条目发表在未分类分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注