欧几里得算法

又称碾转相除法，用于计算两整数a, b 的最大公约数。
初学C语言时写的代码：

#include <stdio.h>
int main()
{
    int a,b,m,n,x;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        if(a==b)
            printf("%d %d\n",a,b);
        else if(a!=0&&b!=0)
        {
            x=1;
            if(a>b)
            {
                m=a;
                n=b;
            }
            else if(a<b)
            {
                m=b;
                n=a;
            }
            while(x!=0)
            {
                x=m%n;
                if(x!=0)
                {
                    m=n;
                    n=x;
                }
            }
            printf("%d %d\n",n,a*b/n);
        }
        else if(a==0&&b!=0)
            printf("%d %d\n",b,a);
        else if(a!=0&&b==0)
            printf("%d %d\n",a,b);

    }
    return 0;
}

原理依赖于下面定理：

两个整数的最大公约数等于其中较小的那个数和两数相除的最大公约数。

证明：
设 a = kb +r， 则r = a mod b
假设d为a, b的一个公约数
r = kb - a
r/d = kb/d - a/d
可知r/d为整数，因此d也是a, b, a%b的公约数， 则得证。

欧几里得扩展算法

这里是在学习RSA的共模攻击，所以复习一下欧几里得算法，但是关键是欧几里得算法扩展：

如果gcd(a, b) = c，则存在x, y，使得c = ax + by。

证明：

　　设 a>b
　　当 b = 0时，gcd(a, b) = a，此时x = 1, y = 0。
　　假设 a*x1 + b*y1 = gcd(a, b)
　　则 b*x2 + (a mod b)*y2 = gcd(b, a mod b)
　　根据 gcd(a, b) = gcd(b, a mod b)　　
　　可得 a*x1 + b*y1 = b*x2 + (a mod b)*y2　　
　　因为 a mod b = a - (a/b)*b //这里 ‘/‘ 是整除　　
　　所以 a*x1 + b*y1 = b*x2 + (a - (a/b)*b)*y2 　
　　　　　　　　　　　= b*x2 + a*y2 - (a/b)*b*y2
　　　　　　 gcd(a, b) = a*y2 + b*(x2 - (a/b)*y2)
　　对比 a*x1 + b*y1 = gcd(a, b)　　
　　发现 x1 = y2
　　　 　 y1 = x2 - (a/b)*y2　　

算法代码如下：

int e_gcd(int a, int b, int x, int y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int ans = e_gcd(b, a%b, x, y);
    int t = x;
    x = y;
    y = x - (a/b)*y;
    return ans;
}

扩展欧几里德算法不但能计算gcd(a, b)，还可以求解形如a*x + b*y = c 的通解，但是求通解吊意思也没，所以这里来求一个特殊的解，乘法逆元。

乘法逆元

什么叫乘法逆元？

形如ax≡1(mod b)
我们称x是a关于f的乘法逆元，还有另一种表达式：

a*x + b*y = 1  

也就是gcd(a, b) = 1

在RSA共模攻击中，求乘法逆元函数如下

def egcd(a, b):
    if a == 0:
          return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)