1．編程實(shí)現(xiàn)：輸入兩個(gè)整數(shù)a和b，利用歐幾里德算法計(jì)算兩個(gè)整數(shù)的大公因子gcd(a,b)。
2. 編程實(shí)現(xiàn)歐幾里德擴(kuò)展算法，計(jì)算gcd(a,b)=ax+by中的x和y。其中一個(gè)整數(shù)a是你的學(xué)號(hào)，另一個(gè)整數(shù)為素?cái)?shù)p= f4f47f05794b256174bba6e9b396a7707e563c5b，求整數(shù)a在模p下的逆元。
一臺(tái)PC，安裝Windows 10操作系統(tǒng)及VC++\Python開發(fā)環(huán)境等。
六、實(shí)驗(yàn)思路，代碼及運(yùn)行結(jié)果： 1．解題思路或方法：歐幾里德算法：
眾所周知，歐幾里得算法gcd是用來求兩個(gè)整數(shù)的大公因子。其中g(shù)cd（a,0）或gcd（0，b）分別等于a和b。對(duì)于任意兩個(gè)整數(shù)a,b(對(duì)其大小沒有要求，不妨設(shè)a>=b),有g(shù)cd(a,b)=gcd(b,a mod b)，這是歐幾里德算法基本內(nèi)容。只需a mod b等于0時(shí)，此時(shí)式子中的a自然是a和b的大公因子。
歐幾里德拓展算法：
歐幾里得拓展算法是用來計(jì)算乘法逆元的，并且兩個(gè)數(shù)字大公約數(shù)為1。我的學(xué)號(hào)是：XXXXXXXXXX(我的學(xué)號(hào)是7位，就不拿出來展示了，就用X表示了)，素?cái)?shù)p轉(zhuǎn)為十進(jìn)制后結(jié)果為：1398446195032410252040217410173702390108694920283。
既然已知p是素?cái)?shù)，a又比p小，故a與p是互質(zhì)的，符合歐幾里德拓展算法的要求。給出正整數(shù)a和p，擴(kuò)展的歐幾里得算法可以計(jì)算a和p的大公約數(shù)d，同時(shí)得到兩個(gè)整數(shù)x和y滿足：d=gcd(a, b) = ax+by。
根據(jù)擴(kuò)展的歐幾里得算法求乘法逆元：簡單說，如果有：ab mod p = 1成立，則稱a和b互為模p意義下的乘法逆元（a與b均與q互質(zhì)）。若a與p互質(zhì)，那么d=gcd(a, p)=1, 即 ax + py = 1, 于是 py = (-x)a+1
也即：ax(mod p)=1，于是x即為a在模p意義下的乘法逆元。
在歐幾里得算法中，可以把過程寫的更清晰一些：
（仍以d=gcd(a,p)=ax+py為例）
a = q1p + p1, p1=ax1+by1;
p = q2p1 + p2, p2=ax2+by2;
p1 = q3p2 + p3, p3=ax3+by3;
… … … …
p(n-2) = q(n)p(n-1)+p(n), p(n)=ax(n)+by(n)
p(n-1) = q(n+1)p(n)+0
則：p(i-2) = q(i)p(i-1)+p(i)或 p(i) = p(i-2) - p(i-1)q(i)
又p(i-1) = ax(i-1)+by(i-1)且p(i-2) = ax(i-2)+by(i-2)
帶入得：
x(i) = x(i-2)-qx(i-2)
y(i) = y(i-2)-qy(i-2)
求出x（i）（i為大）的值，即為a在模p意義下的乘法逆元。
正常來說完成上述代碼，實(shí)驗(yàn)到這里應(yīng)該結(jié)束了，但是由于實(shí)驗(yàn)所涉及的a和p數(shù)字太大，c語言的代碼并不能
直接運(yùn)算，故在這里我們選擇使用Python進(jìn)行計(jì)算。
歐幾里得算法（c語言)：
重慶分公司
重慶分公司
#includeint gcd(int a, int b)
{ if (b == 0) return a;
else
{return gcd(b, a % b);
}
}
int main()
{int a, b,temp;
scanf_s("%d %d", &a, &b);
if (a< b)
{temp = a;
a = b;
b = temp;
}
temp=gcd(a, b);
printf("%d和%d的大公約數(shù)是%d", a, b, temp);
return 0;
}
根據(jù)擴(kuò)展的歐幾里得算法求乘法逆元：
#includeusing namespace std;
int exgcd(int a, int b, int& x, int& y) {if (b == 0)
{//最里面ax+0=a的情況,注意此時(shí)a經(jīng)過多次遞歸已經(jīng)不是剛開始的啊
x = 1;
y = 0;
return a;
}
//要先調(diào)用ngcd來進(jìn)到最里層確定x，y的值，從逐步到外層計(jì)算出x，y
int ngcd = exgcd(b, a % b, x, y);
//根據(jù)相關(guān)理論有如下的逆公式 x==y1,y==x1-a/b*y1
int temp = x;
x = y;
y = temp - a / b * y;
return ngcd;
}
int inverse(int a, int p) {int x, y, gcd;
gcd = exgcd(a, p, x, y);
if (gcd == 1) {x = (x % p + p) % p;//保證x為正數(shù);
return x;
}
else {cout<< "a,p不互質(zhì)";
return 0;
}
}
int main() {//實(shí)際上是求ax + py = gcd(a,p) = 1 /a,p互質(zhì)
int a, p;
cout<< "請(qǐng)輸入 a p"<< endl;
cin >>a >>p;
cout<< "a mod p的乘法逆元是"<< inverse(a, p);
return 0;
} 將以上的所有c語言代碼轉(zhuǎn)換為Python代碼如下：
a=int(input("請(qǐng)輸入數(shù)字a：\n"))
p=str(input("請(qǐng)輸入數(shù)字p：\n"))
p1=int(p,16)
#print(a,p1) 測試程序是否正確
x=1
y=0
def exgcd(a,b):
global x
global y
if(b==0):
x=1
y=0
return a
ngcd=exgcd(b,a%b)
temp=x
x=y
y=temp-a//b*y
return ngcd
def inverse(a,p):
global x
gcd=exgcd(a,p)
if(gcd==1):
x=(x%p+p)%p
return x
else:
print("a,p不互質(zhì)")
c=inverse(a,p1)
print("a mod p的乘法逆元是：",c)歐幾里得算法：
在Python的基礎(chǔ)上使用擴(kuò)展的歐幾里得算法求乘法逆元：
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
