擴(kuò)展歐幾里德算法計(jì)算乘法逆元

1、擴(kuò)展歐幾里德算法計(jì)算乘法逆元-. 歐幾里德算法歐幾里德算法乂稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b 的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：定理： gcd(a,b) = gcd(b,a mod b) 歐幾里德算法就是根據(jù)這個(gè)原理來做的，其算法用c+祁言描述為：void swap(int & a, int & b) ( int c = a a = b; b = c; int gcd(int a,int b)( if(0 = a )( return b; if( 0 = b)( return a; if(a b)( swap(a,b); int c; for(c = a % b ;

2、 c 0 ; c = a % b)( a = b; b = c; return b; 二. 擴(kuò)展歐幾里德算法乘法逆元模p乘法逆元對(duì)于整數(shù)a、p,如果存在整數(shù)b,滿足ab mod p =1，則說，b是a的模p乘法逆元。定理：a存在模p的乘法逆元的充要條件是gcd(a,p) = 1三. 擴(kuò)展歐幾里德算法如下：#include int gcd(int a, int b , int &ar,int &br) int x1,x2,x3; int y1,y2,y3; int t1,t2,t3; int k; if(0 = a) /有一個(gè)數(shù)為0,就不存在乘法逆元ar = 0; br = 0;

3、 return b; if(0 = b) ( ar = 0; br = 0 ; return a; 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; return 1; else( / 公約數(shù)不為1,無乘法

4、逆元ar = 0; br = 0; return y3; int main()( int a,b; int ar,br; int r; cina ; cin b ; r = gcd(a,b,ar,br); coutn 最大公約數(shù)：rendl; coutn 乘法逆元:arendl; coutn 乘法逆元:brendl; return 0; 四. 程序分析本程序只是很簡(jiǎn)單描述了一般情況下的擴(kuò)展歐幾里德算法乘法逆元，當(dāng)給出的兩個(gè)數(shù)如果最大公因數(shù)不為一時(shí)，則無乘法逆元，將他們的逆元都設(shè)置為0,當(dāng)給出的數(shù)只要有一個(gè)為零，則沒有乘法逆元。五. 序運(yùn)行環(huán)境本程序采用用c+語言編寫，編譯，鏈接，運(yùn)行都是在mingw developer studio 平臺(tái)下進(jìn)行的。六. 程序運(yùn)行結(jié)果如下：354 12 最大公約數(shù)二6乘