資源描述：
《快速指數(shù)取模運(yùn)算與用擴(kuò)展歐幾里得算法求解最大公約數(shù)和求乘法逆元》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、一、實(shí)驗(yàn)1.1源代碼：#includc"stdio.h"#include"stdlib.h"#includeuiostreamMusingnamespacestd;voidModc(inta,intb,intn){intc=l;do{if(a%2==0){a=a/2;b=(b*b)%n;}else{a=a-1;c=(b*c)%n;}}whilc(a!=0);cout?"取余結(jié)果為:M?c?endl;}voidmain(){inta,b,n;cout?"輸入格式范例bAamodn"?endl;cout?"u?endl;cout?H請(qǐng)輸入指數(shù)a：n?endl;
2、cin?a;coutvv"請(qǐng)輸入該基數(shù)b："?endl;cin?b;coutvv"請(qǐng)輸入被除數(shù)n："?endl;cin?n;Mode(a,b,n);二、實(shí)驗(yàn)效果圖:回S3nodn請(qǐng)輸入*旨藪a：37請(qǐng)輸入該基數(shù)b：30請(qǐng)輸入被除數(shù)n：77取余結(jié)果為：2Pressanykeytocontinuenr實(shí)驗(yàn)1.2用擴(kuò)展歐幾里得算法求解最大公約數(shù)和求乘法逆元一、實(shí)驗(yàn)1.2源代碼：#includeintextended_Gcd(inta,intb,int&x,int&y)〃求最大公約數(shù){if(b==0){x=1;y=o；returna;}else{
3、intged=extended_Gcd(b,a%b,x,y);intt=x;x二y;y=t-(a/b)*y;returnged;}}intextended_Ivn(intf,intd,int^result)〃求乘法逆元{intxl,x2,x3,yl,y2,y3,tl,t2,t3,q;xl=y2=1;x2=yl=0;x3=(f>=d)?f:d;y3=(f>=d)?d:f;while(1){if(y3==0){Result=x3;//兩個(gè)數(shù)不互索則result為兩個(gè)數(shù)的最大公約數(shù)，此時(shí)返回值為零return0;if(y3==1)^result=y2;〃兩個(gè)數(shù)互
4、素則resutl為其乘法逆元，此吋返冋值為1return1;q=x3/y3;tl=xl-q*yl;t2=x2-q*y2;t3=x3-q*y3;xl=yl;x2=y2;x3=y3;yl=tl;y2=t2；y3=t3；intmain(){intx,y,z;inta,b;int*p,*q;p=&x;q=&y;z=0;printf(”請(qǐng)輸入兩個(gè)數(shù):”);scanf(,,%d%du,&a,&b);if(extended_Gcd(a,b?*p,*q)==1){extended_Ivn(a,b,&z);printf("%d和％＜1互素,乘法的逆元是:%d",a,b,
5、z);}else{z=extended_Gcd(a,b,*p,*q);printf(n%d和％＜1不互素，最大公約數(shù)為:%dM,a,b,z);}return0;二、實(shí)驗(yàn)效果圖:El"C:UsersSorrelDesktop^f^$；^^Debug^^l.2.exe"■3?C:UsersSoirelDesktop新建文件夾Debug^驗(yàn)l?2.exe”1=IfaIf231請(qǐng)輸入兩個(gè)數(shù)「12344321>1234和4321互素，乘法的逆兀是：-1082二Pressanykeytocontinue■3"C:UsersSorrel
6、DesktopWr^^{i^Debug^^1.2.exe,'劇磁,詼元是:劇Pressanykeytocontinue
