实验二、密码学基本算法的实现(二) 2.doc

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