扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。因此，有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数；然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的一组整数特解。

以下是扩展欧几里得算法的python实现：

1.递归

#扩展欧几里得算法 
def ext_gcd(a, b):    
    if b == 0:          
        return 1, 0, a     
    else:         
        x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)        
        x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立         
        return x, y, gcd

2.非递归

print("请输入一个整数：")
a = int(input())
print("请输入模？")
m = int(input())

if a < m:
    a, m = m, a
    x1, x2,x3= 1, 0, a
    y1, y2,y3= 0, 1, m
    while y3 != 0:
        Q = x3//y3
        t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
        x1, x2, x3 = y1, y2, y3
        y1, y2, y3 = t1, t2, t3
    print(x2)
else:
    x1, x2, x3 = 1, 0, a
    y1, y2, y3 = 0, 1, m
    while y3 != 0:
        Q = x3 // y3
        t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
        x1, x2, x3 = y1, y2, y3
        y1, y2, y3 = t1, t2, t3
    print(x1)

以下是两种方法的运行验证结果


说明以上代码正确有效。

欧几里得算法

背景知识：

        欧几里得算法：又叫做辗转相除法，用来求两个数的最大公约数。通过辗转相除，当余数为0的时候，最后的除数就是两个数的最大公约数。

 例如：求20和11的最大公约数

每次将除数作为下一个式子的被除数，将余数作为下一个式子的除数。

        20➗11=1......9

        11➗9=1......2

        9➗2=4......1

        2➗1=2......0

所以最大公约数为最后一个式子的除数1，即gcd(20，11)=1

扩展欧几里得算法与逆元

        扩展欧几里得算法结论：对整数 a 与 b来说, 必存在整数 x 与 y 使得

                                                   ax + by = gcd(a,b)

        注：具体证明此处不做展开

 逆元定义：ax = 1(mod p)，此时a与x互为逆元

例如a = 4，p = 11，由于4*3=12,12 mod 11 = 1,a=4在模11条件下的逆元为x=3。

为什么扩展欧几里得算法可以求解逆元：

        由逆元定义可知满足ax%p=1，因此a与b互为逆元时，加上k倍的p也不影响，毕竟kp对p取余之后为0,所以可以将求逆元的过程转换成：ax+kp=1,此时a与p已知，这就成功转化成扩展欧几里得算法求解的形式，我们可以求出x和k，x即为a对应的逆元。

对于复杂式子我们不能直接看出对应的逆元，具体操作步骤如下所示。

 例如：求11在(mod20)条件下的逆元

        上个例子中求得：gcd(20，11)=1

  代入扩展欧几里得式子：

        11x+20y=1

具体求解方法如下所示（类似于欧几里得算法求解过程）：

        20=11*1+9                               ----------①

        11=9*1+2                                 ----------②

        9=2*4+1                                  ----------③

 写成上述的形式是类似于计算机求解过程，因此下面的移向操作并不是多此一举。

由式子①，②（移项）可得：

        20-11*1=9                                  ----------④

        11-9*1=2                                    ----------⑤

④带入⑤（目的是消去9，当求解过程中有很多式子时，就是这样一步步消去中间项）

        11-（20-11*1）*1=2                   ----------⑥

再将④和⑥代入③消去中间值9和2，可得：

        20-11*1=（11-（20-11*1）*1）*4+1

合并同类项可得：

        5*20-9*11=1

也就解除了最开始的式子11x+20y=1，得到x=-9,y=5

总结：对式子ax = 1(mod p)我们已知a和p，先求p=a*x1+p1（此时的p1实际上时p与a运算的余数）,然后将p=a,a=p1代入式子不断进行迭代，直到计算出余数为1时，pi=a*xi+1,就可以不断移向消去中间项，最后计算出对应的逆元。

 乘法密码

 答疑：

        图中是以英文字母为例，假设26个字母对应数字0-25

1.为什么k要与26互素

        因为互素的条件下才能将0-25与k运算之后均匀的映射到每一个位置，否则肯定会有重叠的部分。

2.怎么求k的逆元

        由于k与26互素，所以gcd（k，26）=1.

        已知k和p=26，利用扩展欧几里得算法：kx+py=1可求得x,y，此时x即为对应的逆元。