本頁使用了標題或全文手工轉換

擴展歐幾里得算法

維基百科,自由的百科全書
跳至導覽 跳至搜尋

擴展歐幾里得算法(英語:Extended Euclidean algorithm)是歐幾里得算法(又叫輾轉相除法)的擴展。已知整數a、b,擴展歐幾里得算法可以在求得a、b的最大公因數的同時,能找到整數x、y(其中一個很可能是負數),使它們滿足貝祖等式

如果a是負數,可以把問題轉化成

為a的絕對值),然後令

通常談到最大公因數時,我們都會提到一個非常基本的事實(由裴蜀定理給出):給定二個整數a、b,必存在整數x、y使得ax + by = gcd(a,b)[1]

眾所周知,已知兩個數,對它們進行輾轉相除(歐幾里得算法),可得它們的最大公因數。不過,在歐幾里得算法中,我們僅僅利用了每步帶餘除法所得的餘數。擴展歐幾里得算法還利用了帶餘除法所得的商,在輾轉相除的同時也能得到裴蜀等式[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

證明[編輯]

由於序列是一個遞減序列,所以本算法可以在有限步內終止。又因為的最大公因數是一樣的,所以最終得到的的最大公因數。

在歐幾里得算法正確性的基礎上,又對於有等式成立(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 <stdio.h>

//这里用了int类型,所支持的整数范围较小且本程序仅支持非负整数,可能缺乏实际用途,仅供演示。
struct EX_GCD { //s,t是裴蜀等式中的系数,gcd是a,b的最大公约数
	int s;
	int t;
	int gcd;
};

struct EX_GCD extended_euclidean(int a, int b) {
	struct EX_GCD ex_gcd;
	if (b == 0) { //b等于0时直接结束求解
		ex_gcd.s = 1;
		ex_gcd.t = 0;
		ex_gcd.gcd = 0;
		return ex_gcd;
	}
	int old_r = a, r = b;
	int old_s = 1, s = 0;
	int old_t = 0, t = 1;
	while (r != 0) { //按扩展欧几里得算法进行循环
		int q = old_r / r;
		int temp = old_r;
		old_r = r;
		r = temp - q * r;
		temp = old_s;
		old_s = s;
		s = temp - q * s;
		temp = old_t;
		old_t = t;
		t = temp - q * t;
	}
	ex_gcd.s = old_s;
	ex_gcd.t = old_t;
	ex_gcd.gcd = old_r;
	return ex_gcd;
	}

int main(void) {
	int a, b;
	printf("Please input two integers divided by a space.\n");
	scanf("%d%d", &a, &b);
	if (a < b) { //如果a小于b,则交换a和b以便后续求解
		int temp = a;
		a = b;
		b = temp;
	}
	struct EX_GCD solution = extended_euclidean(a, b);
	printf("%d*%d+%d*%d=%d\n", solution.s, a, solution.t, b, solution.gcd);
	printf("Press any key to exit.\n");
	getchar();
	getchar();
	return 0;
}

參考資料[編輯]

  1. ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25] (中文(台灣)‎). 
  2. ^ Kenneth H.Rosen; 徐六通 楊娟 吳斌 譯. 離散數學及其應用 原書第七版. : 232頁. ISBN 978-7-111-45382-6. 

參考文獻[編輯]

外部連結[編輯]