扩展欧几里得算法(英语:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式:
ax + by = gcd(a, b)
如果a是负数,可以把问题转化成:
|a|(-x) + by = gcd(|a|, x) (|a|为a的绝对值,然后令x' = (-x)。
通常谈到最大公约数时,我们都会提到一个非常基本的事实(贝祖等式给定):给定二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b)。
众所周知,已知两个数a和b,对它们进行辗转相除,可得它们的最大公约数。不过,在欧几里得算法中,我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商,在辗转相除的同时也能得到贝祖等式中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。
另外,扩展欧几里得算法是一种自验证算法,最后一步得到的si+1和ti+1(si+1和ti+1的含义如下)乘以gcd(a,b)之后恰好是a和b,可以用来验证计算结果是否正确。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元),求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。
在标准的欧几里得算法中,我们记欲求最大公约数的两个数为a和b,第i步带余除法得到的商为qi,余数为ri+1,则欧几里得算法可以写成如下形式:
r0 = a
r1 = b
.......
ri+1 = ri-1 - qi ri 且 0 ≤ ri+1 < |ri|
......
当某步得到的 ri+1 = 0 时,计算结束。上一步得到的ri即为a,b的最大公约数。
扩展欧几里得算法在qi,ri的基础上增加了两组序列,记作si和ti,并s0 = 1, s1 = 0, t0 = 0, t1 = 1,在欧几里得算法每步计算ri+1 = ri-1 - qi ri 之外额外计算
si+1 = si-1 - qi si 和 ti+1 = ti-1 - qi ti,亦即:
r0 = a r1 = b
s0 = 1 s1 = 0
t0 = 0 t1 = 1
...... ......
ri+1 = ri-1 - qi ri 且 0 ≤ ri+1 < |ri|
si+1 = si-1 - qi si
ti+1 = ti-1 - qi ti
......
算法结束条件与欧几里得算法一致,也是ri+1 = 0,此时所得的si 和 ti 即满足等式gcd(a, b) = ri = asi + bti。
下表以a = 240,b = 46为例演示了扩展欧几里得算法:
序号 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 |
所得的最大公因数是2,所得贝祖等式为gcd(240, 46) = 2 = -9* 240 + 47 * 46。同时还有自验证等式|23| * 2 = 46 和 |-120| * 2 = 240。
以下是扩展欧几里德算法的Rust实现:
1 pub fn extend_euclidean(a: isize,b: isize)->(isize,isize,isize){ 2 if b == 0{ 3 return ( 1,0,a); 4 }else { 5 let (mut old_r,mut r) = (a,b); 6 let (mut old_s,mut s) = (1,0); 7 let (mut old_t,mut t) = (0,1); 8 while r != 0{ 9 let q = old_r/r; 10 11 let temp = old_r; 12 old_r = r; 13 r = temp - q*r; 14 15 let temp = old_s; 16 old_s = s; 17 s = temp - q*s; 18 19 let temp = old_t; 20 old_t = t; 21 t = temp - q*t; 22 } 23 (old_s,old_t,old_r) 24 } 26 }
模逆元Rust实现:
1 pub fn mod_inverse(a: isize,n:isize)->Option<isize>{ 2 let (s,_t,gcd) = extend_euclidean(a,n); 3 if gcd != 1{ 4 return None; 5 } 6 if s > 0{ 7 Some(s) 8 }else { 9 Some(s+n) 10 } 11 }
扩展欧几里得算法以及模逆元测试代码:
1 #[test] 2 fn ext_gcd_test(){ 3 let a = 7; 4 let n = 977; 5 let (s,t,gcd) = extend_euclidean(a,n); 6 assert_eq!((-279,2,1),extend_euclidean(7,977)); 7 8 assert_eq!(mod_inverse(47,977),Some(686)); 9 10 }