扩展欧几里德算法计算乘法逆元

《扩展欧几里德算法计算乘法逆元》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、扩展欧几里德算法计算乘法逆元一．欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：定理：gcd(a,b)=gcd(b,amodb)欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：voidswap(int&a,int&b){intc=aa=b;b=c;}intgcd(inta,intb){if(0==a){returnb;}if(0==b){returna;}if(a>b){swap(a,b);}intc;for(c=a%b;c>0;c=a%b){a=b;b=c;}returnb;}一．扩展欧几里德算法乘法逆元模P乘法逆元对于

2、整数a、p，如果存在整数b，满足abmodp=1，则说，b是a的模p乘法逆元。定理：a存在模p的乘法逆元的充要条件是gcd(a,p)=1二．扩展欧几里德算法如下：#includeintgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;intk;if(0==a){//有一个数为0，就不存在乘法逆元ar=0;br=0;returnb;}if(0==b){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;for(t3=x3%y3;t3!=0;t3=

3、x3%y3){k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x1=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==1){//有乘法逆元ar=y2;br=x1;return1;}else{//公约数不为1，无乘法逆元ar=0;br=0;returny3;}}intmain(){inta,b;intar,br;intr;cin>>a;cin>>b;r=gcd(a,b,ar,br);cout<<"最大公约数:"<

4、;}四．程序分析本程序只是很简单描述了一般情况下的扩展欧几里德算法乘法逆元，当给出的两个数如果最大公因数不为一时，则无乘法逆元，将他们的逆元都设置为0，当给出的数只要有一个为零，则没有乘法逆元。五．序运行环境本程序采用用C＋＋语言编写，编译，链接，运行都是在MinGWDeveloperStudio平台下进行的。六．程序运行结果如下：