扩展欧几里得算法

扩展欧几里得算法（）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式。如果a是负数，可以把问题转化成（为a的绝对值），然后令。

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

另外，扩展欧几里得算法是一种自验证算法，最后一步得到的和（和的含义见下文）乘以后恰为和，可以用来验证计算结果是否正确。

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

 算法和举例 
在标准的欧几里得算法中，我们记欲求最大公约数的两个数为，第步带余除法得到的商为，余数为，则欧几里得算法可以写成如下形式：

当某步得到的时，计算结束。上一步得到的即为的最大公约数。

扩展欧几里得算法在，的基础上增加了两组序列，记作和，并令，，，，在欧几里得算法每步计算之外额外计算和，亦即：

算法结束条件与欧几里得算法一致，也是，此时所得的和即满足等式。

下表以，为例演示了扩展欧几里得算法。所得的最大公因数是，所得贝祖等式为。同时还有自验证等式和。

 序号 i    ti 0    0 1      1 2  ÷  =  −  ×  =  −  ×  =  0 −  × 1 = −5 3  ÷  =  −  ×  =  −  ×  =  1 −  × −5 = 21 4  ÷  =  −  ×  =  −  ×  =  −5 −  × 21 = −26 5  ÷  =  −  ×  =  −  ×  =  21 −  × −26 =  6  ÷  =  −  ×  =  −  ×  =  −26 −  × 47 = 

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

得到

 证明 
由于，序列是一个递减序列，所以本算法可以在有限步内终止。又因为， 和的最大公约数是一样的，所以最终得到的是，的最大公约数。

在欧几里得算法正确性的基础上，又对于和有等式成立（i = 0 或 1）。这一关系由下列递推式对所有成立：

因此和满足裴蜀等式，这就证明了扩展欧几里得算法的正确性。
 实现 
以下是扩展欧几里德算法的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) 

Category:数论算法
Category:带有伪代码示例的条目
Category:欧几里得