当前位置: 代码迷 >> 综合 >> 欧几里得算法(求最大公因子)及扩展欧几里得(求乘法逆元)
  详细解决方案

欧几里得算法(求最大公因子)及扩展欧几里得(求乘法逆元)

热度:53   发布时间:2023-09-29 18:06:28.0

一、欧几里得算法

 

欧几里得算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。gcd(a,b)=gcd(b,a mod b)

算法描述:

1. 输入:两个非负整数a,b,且a≥b

2. 输出:a,b的最大公因子。

       (1)b≠0时,作

    r←a mod ba←bb←r

       (2) 返回(a)

代码递归实现:

int gcd(int a,int b)
{//如果a小于bif(a<b){int temp=a;a=b;b=temp;}if(b==0)return a;else return gcd(b,a%b);//递归
}

二、扩展欧几里得算法

 

扩展欧几里德算法是用来在已知a, b求解一组xy,使它们满足贝祖等式: ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。

    递推算法:

输入:两个非负整数a,ba≥b

输出:d=gcd(a,b)与满足ax+by=d的整数xy

1. b=0,则d←ax=1y=0返回(d,x,y)

2. x2←1x1=0y2=1y1=1

3. b>0时,作

       (1) q←a/br←a-qbx←x2-qx1y←y2-qy1。

       (2) a←bb←rx2←x1x1←xy2←y1y1←y

4. d←ax←x2y=y2,返回(d,x,y)

 

递归算法推导:

a>b

1,显然当 b=0gcdab=a。此时 x=1y=0

2a>b>0

ax1+ by1= gcd(a,b);

bx2+ (a mod b)y2= gcd(b,a mod b);

据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);

:ax1+ by1= bx2+ (a mod b)y2;

:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;

说明: a-[a/b]*b即为mod运算。[a/b]代表取小于a/b的最大整数。

也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);

根据恒等定理得:x1=y2; y1=x2- [a / b] *y2;

这样我们就得到了求解 x1,y1 的方法:x1y1 的值基于 x2y2.

上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

乘法逆元:

gcd(r,m)=1,则存在整数s,使得rs1(mod m) 。整数s也称为r模整数m下的乘法逆元。那么当gcd(a,b)=1,有ax+by = gcd(a, b)=1,那么通过计算得出(b+x%b)%b的值就是ab模下的乘法逆元。

递推代码实现:

int gcd(int a,int b)
{//如果a小于bif(a<b){int temp=a;a=b;b=temp;}if(b==0)return a;else return gcd(b,a%b);//递归
}int ex_Gcd(int a,int b,int &x,int &y)
{int x1=0,x2=1,y1=1,y2=0,q,d,r;//最大公因子d=gcd(a,b);if(b==0){d=a;x=1;y=0;return d;}while(b>0){q=a/b;r=a-q*b;x=x2-q*x1;y=y2-q*y1;a=b;b=r;x2=x1;x1=x;y2=y1;y1=y;}d=a;x=x2;y=y2;return d;}int main()
{int x,y;int a,b;cin>>a>>b;ex_Gcd(a,b,x,y);if(gcd(a,b)==1){cout<<"存在a的乘法逆元:"<<(b+x%b)%b<<endl;}else{cout<<"不存在a的乘法逆元!"<<endl;}cout<<"x:"<<x<<endl;cout<<"y:"<<y<<endl;return 0;
}

递归代码实现:

int gcd(int a,int b)
{//如果a小于bif(a<b){int temp=a;a=b;b=temp;}if(b==0)return a;else return gcd(b,a%b);//递归
}int ex_Gcd(int a, int b, int& x, int& y)
{int d;if(b!=0){d = ex_Gcd(b, a % b, y, x);//cout<<"a:"<<a<<endl;//cout<<"b:"<<b<<endl;//cout<<"x:"<<x<<endl;// cout<<"y:"<<y<<endl<<endl<<endl;y = y-(a / b) * x;}else {x = 1;y = 0;}return d;
}int main()
{int x,y;int a,b;cin>>a>>b;ex_Gcd(a,b,x,y);if(gcd(a,b)==1){cout<<"存在a的乘法逆元:"<<(b+x%b)%b<<endl;}else{cout<<"不存在a的乘法逆元!"<<endl;}cout<<"x:"<<x<<endl;cout<<"y:"<<y<<endl;return 0;
}