扩大欧几里德算法计算乘法逆元[指南].doc

文档介绍：扩大欧几里德算法计算乘法逆元[指南]扩展欧几里德算法计算乘法逆元一(欧几里德算法欧几里德算法又称辗转相除法,用于计算两个整数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乘法逆元对于整数a、p,如果存在整数b,满足abmodp=1,则说,b是a的模p乘法逆元。定理:a存在模p的乘法逆元的充要条件是gcd(a,p)=1三(扩展欧几里德算法如下:#include<>intgcd(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=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;