扩展的欧几里得算法

最近的密码学实验，要求模逆，以前都没认真的研究过扩展的欧几里得算法，就趁着这个机会，把扩展的欧几里得算法好好的研究了一番；

扩展的欧几里得算法的应用范围也很广泛:1.可以用来求解不定方程的解。2.可以用来求解模线性方程（线性同余方程）3.求解模的逆元。

由这个名称我们就可以得知，这个算法是对欧几里得算法的扩展，欧几里得算法是求两个数的最大公约数，

而扩展的算法就是对上面式子的x,y进行求解。

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

下面给出这个算法的证明：

推理1:当b=0时，gcd（a,b)=a;此时，x=1,y=0;//推理1；

推理2:当a*b!=0时:

设a0*x0+b0*y0=gcd(a0,b0);这里的a0,b0,x0,y0都是其中的一个状态：

有欧几里得算法可得：

下一个状态：a1=b0,b1=a0%b0=a0-(a0/b0)*b0;

a1*x1+b1*y1=gcd(a1,b1);把前面得到的式子代入；

得：b0*x1+a0*y1-(a0/b0)*b0*y1=gad(a1,b1)=gcd(a0,b0);

由上面的过程可以得出：

x0=y1,y0=x1-(a0/b0)b0*y1 //推理2；

这样我们就得到了求解x0,y0的方法，x0,y0基于x1,y1;

上面利用的思想是基于递归的，所有我们就可以得出递归的程序，b=0就是递归的出口；

下面是递归的代码：

#include <iostream>
#include <cstdio>
int ext_gcd(int a,int b,int &x,int &y)
{
    if(b==0)//根据推理1
    {
        x=1;
        y=0;
        return a;
    }
    int r=ext_gcd(b,a%b,x,y);
    int t=y;//推理2
    y=x-(a/b)*y;
    x=t;
    return r;
}
int main()
{
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    ext_gcd(a,b,x,y);
    printf("%d %d\n",x,y);
    return 0;
}
           

可以对照一下递归的欧几里得算法：

int gcd(int a,int b)
{
    if(b==0)
    return a;
 
    else return gcd(b,a%b);
 }
           

相当于就是在中间添加了求x,y的过程。

还可以利用非递归实现：（求模逆的过程），但是通过这种方法求得的模逆可能会出现负数，而模逆的定义要是最小正整数；

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a,int b)//euclid
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void extend_euclid(int f,int d)//非递归版
{
    int x1,x2,x3;
    int y1,y2,y3;
    int q,t1,t2,t3,flag=0;
    x1=1,x2=0,x3=f;
    y1=0,y2=1,y3=d;
    while(1)
    {
        if(flag==1) break;
        if(y3==0)  x3=gcd(f,d);
        else if(y3==1)
        {
            y3=gcd(f,d);
            printf("%d\n",y2);
            flag=1;
        }
        q=x3/y3;
        t1=x1-q*y1;
        t2=x2-q*y2;
        t3=x3-q*y3;
        x1=y1,x2=y2,x3=y3;
        y1=t1,y2=t2,y3=t3;
    }
}
int main()
{
    int a,b;
    printf("输入要进行模逆运算的两个数:\n");
    scanf("%d%d",&a,&b);
    extend_euclid(a,b);
    return 0;
}
           

别人写的非递归程序：（比较精简）

int exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}
           

参考了 http://www.acmerblog.com/extend-gcd-5610.html