实验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)
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 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;
cout<<"请输入指数a："<<endl;
cin>>a;
cout<<"请输入该基数b："<<endl;
cin>>b;
cout<<"请输入被除数n："<<endl;
cin>>n;
Mode(a,b,n);
}
二、实验效果图：
实验1.2用扩展欧几里得算法求解最大公约数和求乘法逆元
一、实验1.2源代码：
#include <stdio.h>
y3 = (f >= d) ? d : f;
while (1)
{
if (y3 == 0)
{
*result = x3; //两个数不互素则result为两个数的最大公约数，此时返回值为零
return 0;
}
if (y3 == 1)
{
*result = y2; //两个数互素则resutl为其乘法逆元，此时返回值为1
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;
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;
}
二、实验效果图：
{
a=a/2;
b=(b*b)%n;
}
else
{
a=a-1;
c=(b*c)%n;
}
}while(a!=0);
cout<<"取余结果为："<<c<<endl;
}
void main ()
{
int a, b, n;
cout<<"输入格式范例b^a mod n"<<endl;
cout<<"........................................................."<<endl;