快速指数取模运算与用扩展欧几里得算法求解最大公约数和求乘法逆元

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取余结果为:,cendl;void main 0int a, b, n;coutM输入格式范例 l/a mod nHendl;coutMHendl;cout请输入指数a： endl;ciiia;cout请输入该基数b： Hendl

2、;ciiib;cout请输入被除数n： Hendl;ciiin;Mode(a,bji);二.实验效果图:E C:UsersSorrelDesktQPgfrnDebugl.l.exe-MJ C:U5er5SorrelDesktopf$I#Debugl.l.&x. | = |1 B w输入格式范例bJ nod n411请输入指数&：37请输入该基数h ：30请输入被除数n：77取余结果为：2Press ant/ key to continue实验L2用扩展欧几里得算法求解最大公约数和求乘法逆元一、实验12源代码:#include mt extended_Gcd(mt a.iiit b, iiit

3、&x, mt &y) 求最人公约数 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;/两个数不互素则result为两个数的最大公约数，此时返回值为零retuin 0;if (y3 = 1)*result = y2; 两个数互素则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;请输入两个数：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不互素，最人公约数为：diT, a, b, z); return 0;二.实验效果图:Press an 1/ key to cont inue3 ”C:UsersSorrelDesktop新件知Debug篌验l2exe”1 II S II S3 1请输两个数：24140 1676224140和16762不互素，最大公约数为：34Press any key to continuePress an 1/ key to cont inuePress an 1/ key to c