扩展欧几里得算法

(重定向自擴展歐幾里得演算法

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

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

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

扩展欧几里得算法可以用来计算模反元素,求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。

算法和举例

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

 

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

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

 

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

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

序号 i qi−1 余数 ri si ti
0 240 1 0
1 46 0 1
2 240 ÷ 46 = 5 2405 × 46 = 10 15 × 0 = 1 0 − 5 × 1 = −5
3 46 ÷ 10 = 4 464 × 10 = 6 04 × 1 = −4 1 − 4 × −5 = 21
4 10 ÷ 6 = 1 101 × 6 = 4 11 × −4 = 5 −5 − 1 × 21 = −26
5 6 ÷ 4 = 1 61 × 4 = 2 −41 × 5 = −9 21 − 1 × −26 = 47
6 4 ÷ 2 = 2 42 × 2 = 0 52 × −9 = 23 −26 − 2 × 47 = −120

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

 [3]

得到 

证明

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

在欧几里得算法正确性的基础上,又对于  有等式 成立(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;
}

参考资料

  1. ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25]. (原始内容存档 (PDF)于2021-01-24) (中文(臺灣)). 
  2. ^ Kenneth H.Rosen; 徐六通 杨娟 吴斌 译. 离散数学及其应用 原书第七版. 2015-01-01: 232页. ISBN 978-7-111-45382-6. 
  3. ^ 張慧玲. 介紹多項式帶餘除法的矩陣形式及其應用. 太原大學教育學院學報. 2014, (1): 第103–105頁 [2016-03-02]. (原始内容存档于2022-12-14). 

參考文獻

外部連結