快速指數(shù)取模運算與用擴展歐幾里得算法求解最大公約數(shù)和求乘法逆元

1、一、實驗1.1源代碼：#include stdio.1T#include stdlib.h#include HiostreamHusing namespace std;void Mode(iiit a, mt b, mt n)int c=l;do取 a%2=0)a=a/2;b=(b*b)%n;elsea=a-l;c=(b*c)%n;wliile(a!=0);coutM取余結(jié)果為:,cendl;void main 0int a, b, n;coutM輸入格式范例 l/a mod nHendl;coutMHendl;cout請輸入指數(shù)a： endl;ciiia;cout請輸入該基數(shù)b： Hendl

2、;ciiib;cout請輸入被除數(shù)n： Hendl;ciiin;Mode(a,bji);二.實驗效果圖:E C:UsersSorrelDesktQPgfrnDebugl.l.exe-MJ C:U5er5SorrelDesktopf$I#Debugl.l.&x. | = |1 B w輸入格式范例bJ nod n411請輸入指數(shù)&：37請輸入該基數(shù)h ：30請輸入被除數(shù)n：77取余結(jié)果為：2Press ant/ key to continue實驗L2用擴展歐幾里得算法求解最大公約數(shù)和求乘法逆元一、實驗12源代碼:#include mt extended_Gcd(mt a.iiit b, iiit

3、&x, mt &y) 求最人公約數(shù) if(b 0)X=l；y = o；return a;elseint gcd = extended_Gcd(b, a%b, x、y)； int t = x;x = y;v = t - (a / b) * y; return gcd; mt extended_Ivn(iiit f, int d. int *result) 求乘法逆元Ult xl, 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;wliile (1)if (

4、y3 = 0)result = x3;/兩個數(shù)不互素則result為兩個數(shù)的最大公約數(shù)，此時返回值為零retuin 0;if (y3 = 1)*result = y2; 兩個數(shù)互素則resutl為其乘法逆元，此時返回值為1 return 1;q = x3 /y3; tl = xl - q*vl;t2 = x2 - q*v2;t3 = x3 - q*v3; ? ? ?V1V2V31 2 3 t t txl =x2 =x3 =vl =v2 =v3 = mt mam()mt x, y，z ;int a, b;mt *q；p = &x; q = &y; z = 0;請輸入兩個數(shù)：J;scanf(H%d

5、%d, &a. &b);if (extended_Gcd(a,b, *p,*q) = 1)extended_Ivn(a, b, &z);pnntf(”d和1互素，乘法的逆元是：dn”, a, b, z);elsez=extended_Gcd(a,b, *p.*q);printf(”d和d不互素，最人公約數(shù)為：diT, a, b, z); return 0;二.實驗效果圖:Press an 1/ key to cont inue3 ”C:UsersSorrelDesktop新件知Debug篌驗l2exe”1 II S II S3 1請輸兩個數(shù)：24140 1676224140和16762不互素，最大公約數(shù)為：34Press any key to continuePress an 1/ key to cont inuePress an 1/ key to c