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

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