扩展欧几里得算法（）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式ax + by = \gcd(a, b)。如果a是负数，可以把问题转化成\left | a \right |(-x) + by = \gcd(|a|, b)（\left | a \right |为a的绝对值），然后令x'=(-x)。
在欧几里得算法中，我们仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到貝祖等式中的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}，则欧几里得算法可以写成如下形式：
:
\begin{align}
r_0 & =a \\
r_1 & =b \\
& \,\,\,\vdots \\
r_{i+1} & =r_{i-1}-q_i r_i \quad \text {且} \quad 0\le r_{i+1}
当某步得到的r_{i+1}=0时，计算结束。上一步得到的r_i即为a,b的最大公约数。
扩展欧几里得算法在q_i，r_i的基础上增加了两组序列，记作s_i和t_i，并令s_0=1，s_1=0，t_0=0，t_1=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，亦即：
:
\begin{align}
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 {且} \quad 0 & \le r_{i+1}
算法结束条件与欧几里得算法一致，也是r_{i+1}=0，此时所得的s_i和t_i即满足等式\gcd(a,b)=r_i=as_i+bt_i。
下表以a=240，b=46为例演示了扩展欧几里得算法。所得的最大公因数是2，所得贝祖等式为\gcd(240,46)=2=-9240+4746。同时还有自验证等式|23|2=46和|-120|2=240。
這個過程也可以用初等變換表示。
\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}
得到-9\times 240+47\times 46=2
证明
由于 0\le r_{i+1}， r_i 序列是一个递减序列，所以本算法可以在有限步内终止。又因为 r_{i+1}= r_{i-1} - r_i q_i， (r_{i-1}, r_i)和(r_{i}, r_{i+1})的最大公约数是一样的，所以最终得到的 r_k 是a，b的最大公约数。
在欧几里得算法正确性的基础上，又对于 a=r_0和 b=r_1有等式as_i+bt_i=r_i成立（i = 0 或 1）。这一关系由下列递推式对所有i>1成立：
: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_iq_i) + (bt_{i-1}-bt_iq_i) = as_{i+1}+bt_{i+1}
因此s_i和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
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
参考资料
參考文獻
- 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 扩展的欧几里得算法
外部連結
- [http://mathforum.org/library/drmath/view/51675.html Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)]
评论 (0)