扩展欧几里得算法

在标准的欧几里得算法中，我们记欲求最大公约数的两个数为${\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{and}}\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{and }}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}$。

由于${\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 <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;
}

• 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)