扩展欧几里德算法

扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式

ax+by=gcd(a,b)

如果a是负数，可以把问题转化成

|a|(-x) + by = gcd(|a|,b)

然后令x'=(-x)

通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)[1]。

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。

例子

---

用类似辗转相除法，求二元一次不定方程 47x+30y=1

的整数解。

47=30 *1 +17

30=17*1+13

17=13*1+4

13=4*3 +1

然后把它们改写成“余数等于”的形式

17=47*1+30*(-1)

13=30*1 +17*(-1)

4=17*1+13*(-1)

1=13*1+4*(-3)

然后把他们倒回去

1=13*1+4*（-3）

1=13*1+[17*1+13*(-1)] *(-3)

1=17*(-3) +13*4

1=17*(-3) +[30*1+17*(-1)] * 4

1= 30*4 +17 *(-7)

1=30*4 +[47*1+30*(-1)] *(-7)

1= 47*(-7) + 30 *11

得解：

x = -7 y=11

实现

---

def ext_euclid(a, b):

    if b == 0:

        return 1, 0, a

    else:

        x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)

        x, y = y, (x - (a // b) * y)

        print(x,y,q)

        return x, y, q