• 扩展欧几里得算法

　　扩展欧几里得算法（英语：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两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。

另外，扩展欧几里得算法是一种自验证算法，最后一步得到的s_i+1和t_i+1(s_i+1和t_i+1的含义如下)乘以gcd(a,b)之后恰好是a和b,可以用来验证计算结果是否正确。

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

• 算法和举例

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

　　　　　r₀ = a

　　　　　r₁ = b

 　　　　　.......

　　　　r_i+1 = r_i-1 - q_i r_i   且 0 ≤ r_i+1 < |r_i|

　　　　　 ......

当某步得到的 r_i+1 = 0 时，计算结束。上一步得到的r_i即为a，b的最大公约数。

扩展欧几里得算法在q_i，r_i的基础上增加了两组序列，记作s_i和t_i，并s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1，在欧几里得算法每步计算r_i+1 = r_i-1 - q_i r_i 之外额外计算

s_i+1 = s_i-1 - q_i s_i 和 t_i+1 = t_i-1 - q_i t_i，亦即:

 　　　　r₀ = a　　　　　　r₁ = b

　　　　 s₀ = 1　　　　　　s₁ = 0

　　　　 t₀ = 0　　　　　　t₁ = 1

　　　　   ......                    ......

　　　r_i+1 = r_i-1 - q_i r_i   且 0 ≤ r_i+1 < |r_i|　　

 　　  s_i+1 = s_i-1 - q_i s_i 

　　   t_i+1 = t_i-1 - q_i t_i 

　　　　  ......  

算法结束条件与欧几里得算法一致，也是r_i+1 = 0，此时所得的s_i 和 t_i 即满足等式gcd(a, b) = r_i = as_i + bt_i。

下表以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     }