扩展欧几里得算法

Template:NoteTA 扩展欧几里得算法（Template:Lang-en）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式$ax+by=\gcd (a,b)$。如果a是负数，可以把问题转化成$\left|a\right|(-x)+by=\gcd (|a|,b)$（$\left|a\right|$为a的绝对值），然后令$x^{\prime }=(-x)$。

在欧几里得算法中，我们仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到貝祖等式中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。

另外，扩展欧几里得算法是一种自验证算法，最后一步得到的$s_{i+1}$和$t_{i+1}$（$s_{i+1}$和$t_{i+1}$的含义见下文）乘以$\gcd (a,b)$后恰为$a$和$b$，可以用来验证计算结果是否正确。

扩展欧几里得算法可以用来计算模逆元，而计算模逆元是RSA加密算法中生成公钥、私钥的必要步骤。

算法和举例

在标准的欧几里得算法中，我们记欲求最大公约数的两个数为$a,b$，第$i$步带余除法得到的商为$q_i$，余数为$r_{i+1}$，则欧几里得算法可以写成如下形式：

$\begin{array}{cc}{r}_0& =a\\ r_1& =b\\ & ⋮\\ r_{i+1}& =r_{i-1}-q_i{r}_i\text{且}0\le r_{i+1}<|r_i|\\ & ⋮\end{array}$

当某步得到的$r_{i+1}=0$时，计算结束。上一步得到的$r_i$即为$a,b$的最大公约数。

扩展欧几里得算法在$q_i$，$r_i$的基础上增加了两组序列，记作$s_i$和$t_i$，并令$s_0=1$，$s_1=0$，$t_0=0$，$t_1=1$，在欧几里得算法每步计算$r_{i+1}=r_{i-1}-q_i{r}_i$之外额外计算$s_{i+1}=s_{i-1}-q_i{s}_i$和$t_{i+1}=t_{i-1}-q_i{t}_i$，亦即：

$\begin{array}{cccc}{r}_0& =a& r_1& =b\\ s_0& =1& s_1& =0\\ t_0& =0& t_1& =1\\ & ⋮& & ⋮\\ r_{i+1}& =r_{i-1}-q_i{r}_i& \text{且}0& \le r_{i+1}<|r_i|\\ s_{i+1}& =s_{i-1}-q_i{s}_i\\ t_{i+1}& =t_{i-1}-q_i{t}_i\\ & ⋮\end{array}$

算法结束条件与欧几里得算法一致，也是$r_{i+1}=0$，此时所得的$s_i$和$t_i$即满足等式$\gcd (a,b)=r_i=a{s}_i+b{t}_i$。

下表以$a=240$，$b=46$为例演示了扩展欧几里得算法。所得的最大公因数是$2$，所得贝祖等式为$\gcd (240,46)=2=-9*240+47*46$。同时还有自验证等式$|23|*2=46$和$|-120|*2=240$。

序号 i	Template:Blue	Template:Purple	Template:Brown	ti
0		Template:Green	Template:Brown	0
1		Template:Green	Template:Brown	1
2	Template:Green ÷ Template:Green = Template:Blue	Template:Green − Template:Blue × Template:Green = Template:Purple	Template:Brown − Template:Blue × Template:Brown = Template:Brown	0 − Template:Blue × 1 = −5
3	Template:Green ÷ Template:Purple = Template:Blue	Template:Green − Template:Blue × Template:Purple = Template:Purple	Template:Brown − Template:Blue × Template:Brown = Template:Brown	1 − Template:Blue × −5 = 21
4	Template:Purple ÷ Template:Purple = Template:Blue	Template:Purple − Template:Blue × Template:Purple = Template:Purple	Template:Brown − Template:Blue × Template:Brown = Template:Brown	−5 − Template:Blue × 21 = −26
5	Template:Purple ÷ Template:Purple = Template:Blue	Template:Purple − Template:Blue × Template:Purple = Template:Red	Template:Brown − Template:Blue × Template:Brown = Template:Orange	21 − Template:Blue × −26 = Template:Orange
6	Template:Purple ÷ Template:Purple = Template:Blue	Template:Purple − Template:Blue × Template:Purple = Template:Red	Template:Brown − Template:Blue × Template:Brown = Template:Orange	−26 − Template:Blue × 47 = Template:Orange

這個過程也可以用初等變換表示。

$\left(\begin{array}{cc}240& 46\\ 1& 0\\ 0& 1\end{array}\right)\to \left(\begin{array}{cc}10& 46\\ 1& 0\\ -5& 1\end{array}\right)\to \left(\begin{array}{cc}10& 6\\ 1& -4\\ -5& 21\end{array}\right)\to \left(\begin{array}{cc}4& 6\\ 5& -4\\ -26& 21\end{array}\right)\to \left(\begin{array}{cc}4& 2\\ 5& -9\\ -26& 47\end{array}\right)$

得到$-9\times 240+47\times 46=2$

证明

由于$0\le r_{i+1}<|r_i|$，$r_i$序列是一个递减序列，所以本算法可以在有限步内终止。又因为$r_{i+1}=r_{i-1}-r_i{q}_i$， $(r_{i-1},r_i)$和$(r_i,r_{i+1})$的最大公约数是一样的，所以最终得到的$r_k$是$a$，$b$的最大公约数。

在欧几里得算法正确性的基础上，又对于$a=r_0$和$b=r_1$有等式$a{s}_i+b{t}_i=r_i$成立（i = 0 或 1）。这一关系由下列递推式对所有$i>1$成立：

$r_{i+1}=r_{i-1}-r_i{q}_i=(a{s}_{i-1}+b{t}_{i-1})-(a{s}_i+b{t}_i)q_i=(a{s}_{i-1}-a{s}_i{q}_i)+(b{t}_{i-1}-b{t}_i{q}_i)=a{s}_{i+1}+b{t}_{i+1}$

因此$s_i$和$t_i$满足裴蜀等式，这就证明了扩展欧几里得算法的正确性。

实现

以下是扩展欧几里德算法的Python实现：

def ext_euclid(a, b):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = a, b
    if b == 0:
        return 1, 0, a
    else:
        while(r!=0):
            q = old_r // r
            old_r, r = r, old_r-q*r
            old_s, s = s, old_s-q*s
            old_t, t = t, old_t-q*t
    return old_s, old_t, old_r

扩展欧几里得算法C++实现：

#include <bits/stdc++.h>
using namespace std;

int ext_euc(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = ext_euc(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

int main()
{
    int a, b, x, y;
    cin >> a >> b;

    ext_euc(a, b, x, y);
    cout << x << ' ' << y << endl;
    return 0;
}

參考文獻

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 算法导论, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.
• Christof Paar,Jan Pelzl著 马小婷 译. 深入浅出密码学, 清华大学出版社, ISBN 9787302296096. Pages 151-155 6.3.2 扩展的欧几里得算法

外部連結

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) Template:Wayback