q[m]=r[m-1]/r[m];
r[m+1]=r[m-1]-q[m]*r[m];
t[m+1]=t[m-1]-q[m]*t[m];
s[m+1]=s[m-1]-s[m]*s[m];
m++;
}
for(int i=0;i<m;i++)
{
if(q[i]<0)
q[i]=0;
cout<<i<<" r:"<<r[i]<<" q:"<<q[i]<<" s:"<<s[i]<<" t:"<<t[i]<<endl;
1、编写一个函数实现欧几里得算法，并用实例测试程序的正确性。利用该函数计算gcd(1970, 1066)。
欧几里得算法.cpp
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
int main()
{
int a,b,r[30],m,q[30];
}
if(t[m-1]<0)
t[m-1]+=b;
cout<<a<<"的乘法逆元是"<<t[m-1]<<endl;
cout<<"是否继续1继续0停止"<<endl;
cin>>l;
}
return 0;
}
cout<<"请输入两个素数"<<endl;
cin>>a>>b;
r[0]=a;
r[1]=b;
for(int k=0;k<2;k++)
for(int i=2;i<=sqrt(r[k]);i++)
if(r[k]%i==0)
{
cout<<r[k]<<":不是一个素数"<<endl;
exit(0);
}
m=1;
while(r[m]!=0)
{
q[m]=r[m-1]/r[m];
r[m+1]=r[m-1]-q[m]*r[m];
m++;
}
for(int i=1;i<m;i++)
cout<<"q:"<<q[i]<<endl;
cout<<"rm="<<r[m-1]<<endl;
return 0;
}
2、在欧几里得算法的基础上再编写一个函数实现扩展的欧几里得算法。利用该函数编程计算gcd(4655, 12075)和550-1mod1723。
cin>>a>>b;
if (a>b)
{
cout<<"默认的是a<b,所以自动调整位置"<<endl;
tem=a;
a=b;
b=tem;
cout<<a<<" "<<]=a;
t[0]=0;
t[1]=1;
s[0]=1;
s[1]=0;
m=1;
while(r[m]!=0)
{
欧几里德扩展算法.cpp
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
int main()
{
int a,b,m,r[30],q[30],t[30],s[30],l=1,tem;
while(l)
{
cout<<"请输入两个素数"<<endl;
上机实验报告（二）
实验课程：应用密码学实验时间:2013年10月15日
任课教师:刘光军
班级：11级信息与计算科学专业1班姓名：学号：
一、实验名称:密码学基本算法的实现（二）
二、实验目的
通过实验，熟练掌握基本数论算法（欧几里得算法和扩展的欧几里得算法）的计算机实现方法。数论是一门理论与实践结合性很强的课程，在掌握好理论方法的基础之上结合密码学实践，能够加深印象，巩固学习效果。
三、实验内容
1、编程实现欧几里得算法；
2、编程实现扩展的欧几里得算法。
四、实验原理
欧几里德算法又称辗转相除法，用于计算两个整数a, b的最大公约数。其计算原理依赖于下面的定理：
定理：对任何非负的整数a和非负的整数b，有gcd(a, b) = gcd(b, a mod b) (a>=b)。
五、报告正文（文档，数据，模型，程序，图形）