扩展欧几里得算法

扩展欧几里得算法（英語：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式${\displaystyle ax+by=\gcd(a,b)}$。^[1]如果a是负数，可以把问题转化成${\displaystyle \left|a\right|(-x)+by=\gcd(|a|,b)}$（${\displaystyle \left|a\right|}$为a的绝对值），然后令${\displaystyle x'=(-x)}$。

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

另外，扩展欧几里得算法是一种自验证算法，最后一步得到的${\displaystyle s_{i+1}}$和${\displaystyle t_{i+1}}$（${\displaystyle s_{i+1}}$和${\displaystyle t_{i+1}}$的含义见下文）乘以${\displaystyle \gcd(a,b)}$后恰为${\displaystyle a}$和${\displaystyle b}$，可以用来验证计算结果是否正确。

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

算法和举例

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

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{且}}\quad 0\leq r_{i+1}<|r_{i}|\\&\,\,\,\vdots \end{aligned}}}$ 

当某步得到的${\displaystyle r_{i+1}=0}$ 时，计算结束。上一步得到的${\displaystyle r_{i}}$ 即为${\displaystyle a,b}$ 的最大公约数。

扩展欧几里得算法在${\displaystyle q_{i}}$ ，${\displaystyle r_{i}}$ 的基础上增加了两组序列，记作${\displaystyle s_{i}}$ 和${\displaystyle t_{i}}$ ，并令${\displaystyle s_{0}=1}$ ，${\displaystyle s_{1}=0}$ ，${\displaystyle t_{0}=0}$ ，${\displaystyle t_{1}=1}$ ，在欧几里得算法每步计算${\displaystyle r_{i+1}=r_{i-1}-q_{i}r_{i}}$ 之外额外计算${\displaystyle s_{i+1}=s_{i-1}-q_{i}s_{i}}$ 和${\displaystyle t_{i+1}=t_{i-1}-q_{i}t_{i}}$ ，亦即：

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{且}}0&\leq 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}\\&\,\,\,\vdots \end{aligned}}}$ 

算法结束条件与欧几里得算法一致，也是${\displaystyle r_{i+1}=0}$ ，此时所得的${\displaystyle s_{i}}$ 和${\displaystyle t_{i}}$ 即满足等式${\displaystyle \gcd(a,b)=r_{i}=as_{i}+bt_{i}}$ 。

下表以${\displaystyle a=240}$ ，${\displaystyle b=46}$ 为例演示了扩展欧几里得算法。所得的最大公因数是${\displaystyle 2}$ ，所得贝祖等式为${\displaystyle \gcd(240,46)=2=-9*240+47*46}$ 。同时还有自验证等式${\displaystyle |23|*2=46}$ 和${\displaystyle |-120|*2=240}$ 。

序号 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

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

${\displaystyle {\begin{pmatrix}240&46\\1&0\\0&1\end{pmatrix}}\rightarrow {\begin{pmatrix}10&46\\1&0\\-5&1\end{pmatrix}}\rightarrow {\begin{pmatrix}10&6\\1&-4\\-5&21\end{pmatrix}}\rightarrow {\begin{pmatrix}4&6\\5&-4\\-26&21\end{pmatrix}}\rightarrow {\begin{pmatrix}4&2\\5&-9\\-26&47\end{pmatrix}}}$ ^[3]

得到${\displaystyle -9\times 240+47\times 46=2}$ 

证明

由于${\displaystyle 0\leq r_{i+1}<|r_{i}|}$ ，${\displaystyle r_{i}}$ 序列是一个递减序列，所以本算法可以在有限步内终止。又因为${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}}$ ， ${\displaystyle (r_{i-1},r_{i})}$ 和${\displaystyle (r_{i},r_{i+1})}$ 的最大公约数是一样的，所以最终得到的${\displaystyle r_{k}}$ 是${\displaystyle a}$ ，${\displaystyle b}$ 的最大公约数。

在欧几里得算法正确性的基础上，又对于${\displaystyle a=r_{0}}$ 和${\displaystyle b=r_{1}}$ 有等式${\displaystyle as_{i}+bt_{i}=r_{i}}$ 成立（i = 0 或 1）。这一关系由下列递推式对所有${\displaystyle i>1}$ 成立：

${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}}$ 

因此${\displaystyle s_{i}}$ 和${\displaystyle t_{i}}$ 满足裴蜀等式，这就证明了扩展欧几里得算法的正确性。

实现

以下是扩展欧几里德算法的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; 徐六通 杨娟 吴斌 译. 离散数学及其应用 原书第七版. : 232页. ISBN 978-7-111-45382-6.  引文使用过时参数coauthors (帮助)
3. 張慧玲. 介紹多項式帶餘除法的矩陣形式及其應用. 太原大學教育學院學報. 2014, (1): 第103–105頁. 

參考文獻

• 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 扩展的欧几里得算法

外部連結

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) （页面存档备份，存于互联网档案馆）