擴展歐幾里德算法計算乘法逆元

《擴展歐幾里德算法計算乘法逆元》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、擴展歐幾里德算法計算乘法逆元一．歐幾里德算法歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計算兩個整數(shù)a,b的最大公約數(shù)。其計算原理依賴于下面的定理：定理：gcd(a,b)=gcd(b,amodb)歐幾里德算法就是根據(jù)這個原理來做的，其算法用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;}一．?dāng)U展歐幾里德算法乘法逆元模P乘法逆元對于

2、整數(shù)a、p，如果存在整數(shù)b，滿足abmodp=1，則說，b是a的模p乘法逆元。定理：a存在模p的乘法逆元的充要條件是gcd(a,p)=1二．?dāng)U展歐幾里德算法如下：#includeintgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;intk;if(0==a){//有一個數(shù)為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{//公約數(shù)不為1，無乘法逆元ar=0;br=0;returny3;}}intmain(){inta,b;intar,br;intr;cin>>a;cin>>b;r=gcd(a,b,ar,br);cout<<"最大公約數(shù):"<

4、;}四．程序分析本程序只是很簡單描述了一般情況下的擴展歐幾里德算法乘法逆元，當(dāng)給出的兩個數(shù)如果最大公因數(shù)不為一時，則無乘法逆元，將他們的逆元都設(shè)置為0，當(dāng)給出的數(shù)只要有一個為零，則沒有乘法逆元。五．序運行環(huán)境本程序采用用C＋＋語言編寫，編譯，鏈接，運行都是在MinGWDeveloperStudio平臺下進(jìn)行的。六．程序運行結(jié)果如下：