快速指数取模运算与用扩展欧几里得算法求解最大公约数和求乘法逆元
实验1.1 快速指数取模运算
一、实验1.1源代码:
#include "stdio.h" #include "stdlib.h" #include "iostream" using namespace std;
void Mode(int a, int b, int n)
{
int c=1;
do{
if(a%2==0)
{
a=a/2;
b=(b*b)%n;
}
else
{
a=a-1;
c=(b*c)%n;
}
}while(a!=0);
cout<<"取余结果为:"<>a;
cout<<"请输入该基数b:"<>b;
cout<<"请输入被除数n:"<>n;
Mode(a,b,n);
}
二、实验效果图:
实验1.2 用扩展欧几里得算法求解最大公约数和求乘法逆元
一、实验1.2源代码:
#include
int extended_Gcd(int a,int b, int &x, int &y) //求最大公约数 {
if (b == 0)
{
x = 1;
y = 0;
return a;
}
else
{
int gcd = extended_Gcd(b, a%b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return gcd;
}
}
int extended_Ivn(int f, int d, int *result) //求乘法逆元 {
int x1, x2, x3, y1, y2, y3, t1, t2, t3, q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = (f >= d) ? f : d;
y3 = (f >= d) ? d : f;
while (1)
{
if (y3 == 0)
{
*result = x3; // 两个数不互素则result为两个数的最大公约数，此时返回值
为零
return 0;
}
if (y3 == 1)
{
*result = y2; //两个数互素则resutl为其乘法逆元，此时返回值为1
return 1;
}
q = x3 / y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
int main()
{
int x, y, z ;
int a, b;
int *p, *q;
p = &x; q = &y;
z = 0;
printf("请输入两个数: ");
scanf("%d%d", &a, &b);
if (extended_Gcd(a,b, *p, *q) == 1)
{
extended_Ivn(a, b, &z);
printf("%d和%d互素，乘法的逆元是:%d\n", a, b, z);
}
else
{
z=extended_Gcd(a,b, *p, *q);
printf("%d和%d不互素，最大公约数为:%d\n", a, b, z);
}
return 0;
}
二、实验效果图:
本文档为【快速指数取模运算与用扩展欧几里得算法求解最大公约数和求乘法逆元】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483