扩展欧几里得算法
扩展欧几里得算法(英語:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足貝祖等式
如果a是负数,可以把问题转化成
- (为a的绝对值),然后令。
通常談到最大公因數時,我們都會提到一個非常基本的事實(由貝祖定理给出):給定二个整數a、b,必存在整數x、y使得ax + by = gcd(a,b)[1]。
众所周知,已知两个数和,对它们进行辗转相除(欧几里得算法),可得它们的最大公约数。不过,在欧几里得算法中,我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商,在辗转相除的同时也能得到貝祖等式[2](貝祖定理中描述的等式)中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。
另外,扩展欧几里得算法是一种自验证算法,最后一步得到的和(和的含义见下文)乘以后恰为和,可以用来验证计算结果是否正确。
算法和举例编辑
在标准的欧几里得算法中,我们记欲求最大公约数的两个数为 ,第 步带余除法得到的商为 ,余数为 ,则欧几里得算法可以写成如下形式:
当某步得到的 时,计算结束。上一步得到的 即为 的最大公约数。
扩展欧几里得算法在 , 的基础上增加了两组序列,记作 和 ,并令 , , , ,在欧几里得算法每步计算 之外额外计算 和 ,亦即:
算法结束条件与欧几里得算法一致,也是 ,此时所得的 和 即满足等式 。
下表以 , 为例演示了扩展欧几里得算法。所得的最大公因数是 ,所得贝祖等式为 。同时还有自验证等式 和 。
序号 i | 商 qi−1 | 余数 ri | si | ti |
---|---|---|---|---|
0 | 240 | 1 | 0 | |
1 | 46 | 0 | 1 | |
2 | 240 ÷ 46 = 5 | 240 − 5 × 46 = 10 | 1 − 5 × 0 = 1 | 0 − 5 × 1 = −5 |
3 | 46 ÷ 10 = 4 | 46 − 4 × 10 = 6 | 0 − 4 × 1 = −4 | 1 − 4 × −5 = 21 |
4 | 10 ÷ 6 = 1 | 10 − 1 × 6 = 4 | 1 − 1 × −4 = 5 | −5 − 1 × 21 = −26 |
5 | 6 ÷ 4 = 1 | 6 − 1 × 4 = 2 | −4 − 1 × 5 = −9 | 21 − 1 × −26 = 47 |
6 | 4 ÷ 2 = 2 | 4 − 2 × 2 = 0 | 5 − 2 × −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;
}
参考资料编辑
- ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25] (中文(台灣)).
- ^ Kenneth H.Rosen; 徐六通 杨娟 吴斌 译. 离散数学及其应用 原书第七版. : 232页. ISBN 978-7-111-45382-6.
參考文獻编辑
- 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 扩展的欧几里得算法